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.

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

Solution 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 

}

Solution 3

You need a function that returns longest branch in a subtree and the longest path:

PS: I am leaving out details (Eg. Boundary conditions and so on). But this should give you an idea. This function returns two things 'branch' and 'path'. 'branch' is the longest path from this node to any of its leaves. 'path' is the longest path between any two leaves in this subtree.

def longestPath(node):
    (leftBranch, leftPath) = longestPath(node.left);
    (rightBranch, rightPath) = longestPath(node.right);
    if len(rightBranch) > len(leftBranch):
        curBranch = rightBranch+node.name
    else:
        curBranch = leftBranch+node.name

    curPath = leftBranch + node.name + rev(rightBranch)
    bestPath = curPath
    if len(leftPath) > length(bestPath):
        bestPath = leftPath
    if len(rightPath) > length(bestPath):
        bestPath = rightPath

    return (curBranch, bestPath)

Solution 4

defintion:
node: (char content, node left , node right , node parent)
add(list , node): add node as last element in list
remove(list , index): remove and return element at index in list
length(string): length of string
insert(string , char , index): insert char at index in string
concat(string a , string  OR char b): append b to a

input: node start
output: string

start
list nodes
node n

add(nodes , start)

do
    n = remove(nodes , 0)

    if n.parent != null
        add(nodes , n.parent)
    if n.left != null
        add(nodes , n.left)
    if n.right != null
        add(nodes , n.right)
while !isEmpty(nodes)

//n now is the node with the greatest distance to start
string left = ""
string right = ""

node a = start
node b = n

while(a != b)
     insert(left , a.content , length(left) - 1)
     insert(right , b.content , 0)

     a = a.parent
     b = b.parent

string result = left
concat(result , a.content)
concat(result , right)

return result

View more solutions