top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

How to find longest path of a given binary tree?

+8 votes
2,617 views
How to find longest path of a given binary tree?
posted Oct 28, 2013 by Sanketi Garg

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote

Considering the Tree as binary

         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 i.e of length 8.

  1. Calculate the diameter at each node (assuming node as a root of the tree)
  2. Diameter is the height of left subtree + height of right subtree + 1.
  3. Pick the highest diameter amongst all.
answer Oct 29, 2013 by Deepankar Dubey
Check this if this works...
int maxDepth(Node root) {
    if(root == null) {
        return 0;
    } else {
        int ldepth = maxDepth(root.left);
        int rdepth = maxDepth(root.right);
        return ldepth>rdepth ? ldepth+1 : rdepth+1;
    }
}

int longestPath(Node root)
{
   if (root == null)
     return 0;

  int ldepth = maxDepth(root.left);
  int rdepth = maxDepth(root.right);

  int lLongPath = longestPath(root.left);
  int rLongPath = longestPath(root.right);

  return max(ldepth + rdepth + 1, max(lLongPath, rLongPath));
}
Similar Questions
+5 votes
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
0 votes

How to find longest consecutive path in a binary tree using C/C++/Java?

...