@arunachalam you have misunderstood the problem.
On Tue, Mar 27, 2012 at 8:10 AM, Arunachalam <arunachala...@gmail.com>wrote:
> This algorithm is almost right, but not exactly correct.
>
> Say for example you have a binary tree like this
>
> 1
> 2
> 3 4
> 5 6
>
> The length of the longest path is 4, and this algorithm would return 5.
> The algorithm can be slightly modified to find the max path.
>
> Hint: recursively find out the max path for every node assuming it as root
> and you will have a solution.
>
> Thanks,
> Arun.
>
>
>
> On Mon, Mar 26, 2012 at 6:48 AM, 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.
>
--
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.
