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
}
