If the longest path passes through the root of the tree, then the
length of the path is the depth of the left subtree plus the depth of
the right subtree. If the longest path does not pass through the root,
then it is the max of the longest path in the left subtree or the
right subtree.
int longestPath(node *root, int *depth=0)
{
if (root)
{
int depthLeft, depthRight;
int leftResult = longestPath(root->left, &depthLeft);
int rightResult = longestPath(root->right, &depthRight);
if (depth) *depth = 1 + max(depthLeft, depthRight);
return max(leftResult, rightResult, depthLeft+depthRight);
}
else
{
if (depth) *depth = 0;
return 0;
}
}
On Mar 25, 12:37 pm, karthikeyan muthu <keyankarthi1...@gmail.com>
wrote:
> the path we are looking for is surely between two leaf nodes.
>
> start from the root and go to the deepest leaf node.. (dfs/bfs)
>
> from that node traverse the entire tree to find the longest path that
> exists (dfs/bfs)
>
> u can keep track of the last node u visit in two variables for every path
> and update new variables with the optimal path's last visited node ..
>
> this way u get the two required nodes
>
>
>
> On Sun, Mar 25, 2012 at 3:40 PM, Navin Kumar <navin.nit...@gmail.com> wrote:
> > How to find the two most distant nodes in a binary tree.
> > Its not about calculating the diameter of tree, but the two end nodes in
> > the diameter of the tree.
> > Optimal algorithm expected ..
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To view this discussion on the web visit
> >https://groups.google.com/d/msg/algogeeks/-/8pDy6hcBPOUJ.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
