1
\$\begingroup\$

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?
\$\endgroup\$
2
\$\begingroup\$

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.

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

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);
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.