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() &amp; 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.