# Binary Tree Maximum Turns

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?

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.

• 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 :) Nov 16, 2017 at 8:03
• "I cannot imagine a strictly iterative approach." You can use a stack (instead of the call stack).
– Zeta
Nov 16, 2017 at 9:15
• @Zeta Of course, but I consider it cheating. Strictly iterative implies constant memory.
– vnp
Nov 16, 2017 at 17:42

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);
}