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?

Dulcie

max length of the descending path indeed – Dulcie

no, numbers are basically not relevant those could be letters and bst could be just a binary tree, no matter – Dulcie

first you should try to write non-recursive algorithm, then recursive. It will give you imagination where you could save on. – Heartsease

When you say you can't employ recursion, does that mean you're not allowed, or you don't know how? – Timework

I posted a solution without recursion, it is in C# but algorithmically it seems to be correct. On my tests much much more faster. – Aylward

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.

Malpighiaceous

I had no clue that the OP meant this, but reading your answer, it makes a lot of sense! +1 Btw, it's quite useless to drag Results.maxLength all around your tree, while you're only interested in the maximum of left and right on the root. – Darra

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

Aylward

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)

Granvillegranvillebarker

The question states that recursion is not allowed. – Lucier

Answer 4

Here is the working code for the question. An 11-node binary tree is given for testing:

public class Node {

int L = 0;
int R = 0;

Node left = null;
Node right = null;

}

public class BTree {

void calculate_paths(Node root) {

    if (root.left != null) {
        calculate_paths(root.left);
        root.L = root.left.L + 1;
    }

    if (root.right != null) {
        calculate_paths(root.right);
        root.R = root.right.R + 1;
    }
}

int max_paths(Node root) {

    int maxL = 0;
    int maxR = 0;

    if (root.left != null) maxL = max_paths(root.left);
    if (root.right != null) maxR = max_paths(root.right);

    return Math.max(Math.max(root.L, root.R), Math.max(maxL, maxR));

}

}

public class Main {

public static void main(String[] args){
    System.out.println("Let the challenge begin!");

    //create the tree
    Node n0 = new Node();
    Node n1 = new Node();
    Node n2 = new Node();
    Node n3 = new Node();
    Node n4 = new Node();
    Node n5 = new Node();
    Node n6 = new Node();
    Node n7 = new Node();
    Node n8 = new Node();
    Node n9 = new Node();
    Node n10 = new Node();

    n0.right = n1;
    n0.left = n7;

    n1.left = n2;

    n2.left = n3;
    n2.right = n4;

    n4.right = n5;

    n5.right = n6;

    n6.left = n9;
    n6.right = n10;

    n7.left = n8;


    BTree Tree = new BTree();

    Tree.calculate_paths(n0);
    System.out.println(Tree.max_paths(n0));

}

}

Hanlon

Answer 5

Java implementation:

    // auxiliary method, starts the recursion:    

    public int height(){
        if(root != null) // If not null calculate height
            return height(root);
        else // height is zero...
            return 0;
    }

    // Gets the job done:
    private int height(BinaryTreeNode<T> node){

        int right = 0, left = 0;

        if (node.getLeftChild() != null) // count and calculate left path height
            left= 1+ height(node.getLeftChild()); 
        if (node.getRightChild() != null) // count and calculate right path height
            right= 1 + height(node.getRightChild());

        return Math.max(left, right);
    }

Swetlana