Binary Tree Maximum Turns

Question

Given any binary tree, what is the maximum number of turns possible in any path from root to any leaf?

A turn is when the path involves moving from left branch to right or vice-versa; i.e. the number of angels in a path. A straight line path has no turns.

The best I could get is the code below and it works with good performance, looking for better implementation

public class Tree
{
 public int x;
 public Tree l;
 public Tree r;
}
private int leftTurns(Tree T, int turns)
{
 if (T == null)
 return 0;
 return turns += Math.Max(
 leftTurns(T.l, 0),
 rightTurns(T.r, 1));
}
private int rightTurns(Tree T, int turns)
{
 if (T == null)
 return 0;
 return turns += Math.Max(
 leftTurns(T.l, 1),
 rightTurns(T.r, 0));
}
public int solution(Tree T)
{
 // write your code in C# 6.0 with .NET 4.5 (Mono)
 return Math.Max(
 leftTurns(T.l, 0),
 rightTurns(T.r, 0));
}

My concerns:

• The semi-duplicate functions leftTurns() & rightTurns()
• The readability of the algorithm
• Is recursion necessary?

Answer 1

The code duplication is easily eliminated by passing an additional parameter:

 public int solution(Tree T)
 {
 return Math.Max(
 turn(T.l, 0, false),
 turn(T.r, 0, true)
 );
 }
 private int turn(Tree T, int turns, bool it_was_right) {
 if (T == null) {
 return 0;
 }
 return turns += Math.Max(
 turn(T.l, it_was_right, !it_was_right),
 turn(T.r, !it_was_right, it_was_right)
 );
 }

Now it is obvious that for the recursive calls an additional parameter is redundant. Making a helper function with only two parameters is a good exercise.

---

Recursion seems to be necessary. I cannot imagine a strictly iterative approach. At the end of the day you must check every path.

---

A small nitpick. You don't compute angels in the path (that would be quite hard indeed); you compute angles. Sorry, can't resist.

• modeeb: Yes, I tried that. Looks nice in C++, but needed a couple of ugly conversion lines to work in C# Please elaborate more on helper function suggestion Also +1 for your angles note :)
• Zeta: "I cannot imagine a strictly iterative approach." You can use a stack (instead of the call stack).
• vnp: @Zeta Of course, but I consider it cheating. Strictly iterative implies constant memory.

Answer 2

I tried to simulate inOrder traversal, and yes, I used stack as Zeta suggested

Check this one below .. what do you think?

 public int solution(Tree T)
 {
 int max = 0, turns = 0;
 Stack<Tree> stack = new Stack<Tree>();
 bool last_was_left = true;
 bool going_right = false;
 while(true)
 {
 if (T != null)
 {
 if (!(last_was_left ^ going_right))
 turns++;
 stack.Push(T);
 last_was_left = !going_right;
 going_right = false;
 T = T.l;
 }
 else if (stack.Count > 0)
 {
 if (stack.Count == 1) // left branch completed, switch to right branch & reset turns
 {
 last_was_left = false;
 max = Math.Max(max, turns);
 turns = 0;
 }
 T = stack.Pop();
 going_right = true;
 T = T.r;
 }
 else // completed both branches
 break;
 }
 return Math.Max(max, turns);
 }