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.

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