top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

How to find nodes in a tree which has longest path?

+5 votes
317 views
      40
      /\
     20 60
     /\  \
   10 30  80
      /   /\
     25  70 90
           \
           75

longest path 
25 30 20 40 60 80 70 75 
Answer
    25 ----> 75
posted Nov 23, 2013 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

1 Answer

0 votes

Check this but will not tell the nodes only the length of the path...

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));
}
answer Nov 23, 2013 by Salil Agrawal
use floyd warshall's algo after mapping the tree in a matrix. Then calculate the maximum distance.
Similar Questions
+6 votes
The input tree is as shown below
            40
            / \
        20      60
        / \       \
    10      30      80
      \            /  \ 
       15        70    90

Output: 15 30 60 80 90
+7 votes

A binary tree is given and two nodes of this tree is given, we have to find out the algorithm/code for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...