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

algorithm, binary-search-tree, java

Solution

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:

- the length of the left path starting at that node,

- the length of the right path starting at that node, and

- 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`.

Problem

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?

Original source