Print the Longest leaf-to-leaf path in a binary tree along with its length

Question

I am solving a problem in which I have to find the longest leaf-to-leaf path in a binary tree along with its length.

for example, if the Binary tree is as follows:

         a
         /\
        b c
      /   / \
     d   e  f 
    / \      \
   g  h      p
       \
        k

The longest leaf-to-leaf path would be k-h-d-b-a-c-f-p which is of length 8.

I am calculating the length by recursively finding the length of the left and right sub-tree and then return height_left + height_right + 1 . Is my concept correct?.

Also how should I print the longest leaf-to-leaf path? I just want an idea to proceed.

Answer 1

It seems to me that this algorithm is very close to finding a diameter of a binary tree. Diameter of the tree is the number of nodes on the longest path between two leaves in the tree.

I think you can look here for the implementation: http://www.geeksforgeeks.org/diameter-of-a-binary-tree/ and then adapt it or optimize it's time complexity if you want. But i think O(n) is good enough.

Answer 2

Most answers on the net gives how to find diameter of a tree, i.e How to find the number of nodes in the longest path.

The only addition is we need to store the nodes which contribute to it.

In recursion, this can be done in two ways.

a) It should be a return type
b) It should be an input parameter which is an object. This object is populated with the result during the course of recursion.

Without the need to print the longest path, we only need to check at every node:
Max of
1) Left node max path
2) Right node max path
c) Current node max path (requires more inputs)

Now, to calculate current node max path, we need more inputs:

Current node max path needs:

1) Max left node height
2) Max right node height

This can either be stored in the node itself (as height parameter) or can be passed with the recursion.

This will only give diameter/length of the longest path.

Now, to get the path printed, we need to store more info which is:
- List<Nodes> pathList - This contains the nodes which form the longest path so far (Note this may not contain the current node).
- List<Nodes> heightList - This contains the nodes which form the longest height from the node to its leaf.

Finally the algo:

//Inputs and Outputs of the method

class Node{
int value;
Node leftchild;
Node rightchild;
}
class ReturnInfo{
ReturnInfo(){
 maxpathlen = 0;
 maxheight = 0;
 pathList = new ArrayList<Node>();
 heightList = new ArrayList<Node>();
}

int maxpathlen; //current max path
int maxheight; //current max height
List<Nodes> pathList;
List<Nodes> heightList;
}

//Signature public ReturnInfo getMaxPath(Node n);

//Implementation

public ReturnInfo getMaxPath(Node n){
//Base case
if(n==null) return new ReturnInfo();
//This is a bottom up recursion. Info will flow from leaves to root.
//So first recurse and then do the work at this node level
//Recurse left & right
ReturnInfo leftReturnInfo = getMaxPath(n.leftchild);
ReturnInfo rightReturnInfo = getMaxPath(n.rightchild);

//Do work in this recursion or for this node 
ReturnInfo retInfo = new ReturnInfo();

//Update all 4 parameters of returninfo and we are done

retInfo.maxheight = max(leftReturnInfo.maxheight, rightReturnInfo.maxheight) + 1;
//Update retInfo.heightList accordingly
retInfo.heightList = ....

retInfo.maxPathLen = max(leftReturnInfo.maxPathLen, rigthReturnInfo.maxPathLen, leftReturnInfo.maxHeight+rightReturnInfo.maxHeight+1);

//Remember from where maxPathLen came from and update accordingly
retInfo.pathList = .....

return retInfo;//We are done 

}