@Don : it seem that you are calculating diameter of a tree ??
On Mon, Mar 26, 2012 at 7:18 PM, Don <dondod...@gmail.com> wrote:
> 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.
>
>
--
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.
