maximum length of a descending path in a tree which always goes left|right

Question

I'm prepearing for tech interview, so basically learning algorithms from very beginning :) we are given a BST. I need to find the max length of a desc path in it, which always goes left or right In other words, an example tree's descending path is 2, ie 15-10-6

   5
  / \
2     15
     /
    10
   / \ 
  6   14

I'm very new to algorithmic problems.what are my steps to solving this?

My idea was to use DFS and a counter to store the longest path. but I can't figure out how to employ recursion to do the job, whereas recursion seems more natural for this data structure.

any suggestions/directions?

Answer 1

The wording is a little confusing, but I think you mean the maximum of

• the maximum length of a path that starts at any node and then only goes to the left, or
• the maximum length of a path that starts at any node and then only goes to the right.

You do this in two passes, one to find the max left path and one to find the max right path (and then take the max of those two). Or you can do it in a single pass that does both at once.

For every node, you want to know three values:

1. the length of the left path starting at that node,
2. the length of the right path starting at that node, and
3. the length of the longest path starting at that node or one of its descendants.

If you are doing this recursively, this means the recursion should return these three values, probably as a small array or as a simple three-field object.

This would look something like

Results calculate(Tree node) {
    if (node == null) return new Results(0,0,0);
    else {
        Results leftResults = calculate(node.left);
        Results rightResults = calculate(node.right);
        int leftLength = 1 + leftResults.leftLength;
        int rightLength = 1 + rightResults.rightLength;
        int maxLength = Math.max(Math.max(leftLength, rightLength), 
                                 Math.max(leftResults.maxLength, rightResults.maxLength));
        return new Results(leftLength, rightLength, maxLength);
    }
}

and the overall result would just be calculate(root).maxLength.

Answer 2

Non-recursive solution

Actually, this is a problem on Codibility which I was tested for. I am just mentioning a non-recursive solution for the sake of discussing it.

The tree has itself a value which can be modified.

I found a better solution than the recursive solution here but I do not program in Java, so I will put the C# solution which is correct algorithmic wise:

public class Tree
{
    public int x;
    public Tree l;
    public Tree r;
}
class solution
{
    public int solution(Tree T)
    {
        // write your code in C# 5.0 with .NET 4.5 (Mono)
        List<Tree> toProcess = new List<Tree>(10000);

        if (T == null)
            return 0;
        int maxLength = 0;
        T.x = 0;
        toProcess.Add(T);

        while (toProcess.Count != 0)
        {
            Tree currNode = toProcess[toProcess.Count-1];
            toProcess.RemoveAt(toProcess.Count - 1);
            int remainder = currNode.x % 100000;
            if (currNode.l != null)
            {
                currNode.l.x = 1 + remainder;
                maxLength = Math.Max(maxLength, currNode.l.x);
                toProcess.Add(currNode.l);
            }
            if (currNode.r != null)
            {
                currNode.r.x = 100000 + (currNode.x - remainder);
                maxLength = Math.Max(maxLength, currNode.r.x / 100000);
                toProcess.Add(currNode.r);
            }
        }
        return maxLength;
    }
}

This is faster than recusion by multiples if you time it. The idea is at each node, you store a longer length in the children nodes and append them to a list (you could have used a stack if you wanted) to process later. You use the int to store the count. The original problem on Codibility mentioned that there are no more than 10 000 nodes and the max depth is 800.

A last optimisation is to replace my use of 100000 to separate left and right length by a binary shift which would be faster, i.e. use the 16 first bits to store length on the left and the remaining for length on the right, but I did not have enough time to do this as I started with the recursive method.

EDIT: I did the bitwise one, too bad I did not have time to make sure it was correct and submit it because it is much faster than the recursive one:

    public int solution(Tree T)
    {
        // write your code in C# 5.0 with .NET 4.5 (Mono)
        List<Tree> toProcess = new List<Tree>(10000);
        
        int rightmask = 0x0000FFFF;
        int leftmask = ~0x0000FFFF;
        if (T == null)
            return 0;
        int maxLength = 0;
        T.x = 0;
        toProcess.Add(T);

        while (toProcess.Count != 0)
        {
            Tree currNode = toProcess[toProcess.Count-1];
            toProcess.RemoveAt(toProcess.Count - 1);
            
            if (currNode.l != null)
            {
                int leftpart = (currNode.x & leftmask) >> 16;
                int newLength = 1 + leftpart;
                currNode.l.x = newLength << 16;
                maxLength = Math.Max(maxLength, newLength);
                toProcess.Add(currNode.l);
            }
            if (currNode.r != null)
            {
                int rightpart = (currNode.x & rightmask);
                currNode.r.x = 1 + rightpart;
                maxLength = Math.Max(maxLength, currNode.r.x);
                toProcess.Add(currNode.r);
            }
        }
        return maxLength;
    }

Answer 3

Idea:

The recursive function called from node v should return 3 values:

1. Maximum descending path which goes always left or always right in subtree rooted in v

2. Maximum length of path which goes always left starting from v

3. Maximum length of path which goes always right starting from v

Let's call these values respectively (V1, V2, V3)

Base case:

Clearly, for any leaf in the tree, all above values are equal 0.

Recursive call:

Let's consider any internal node v.

Let (L1, L2, L3) be the values returned by a recursive call to left child of v.

Let (R1, R2, R3) be the values returned by a recursive call to right child of v.

Then v, in order to compute (V1, V2, V3) only has to combine results returned from the left and the right child:

V2 is equal to L2 + 1 if the left child exists. Otherwise, it's 0.

V3 is equal to R3 + 1 if the right child exists. Otherwise, it's 0.

V1 is equal to max(L1, R1, V2, V3)