I think we can tweak the standard "find the height of the tree"
program to get the result..
As we know that the 2 extremes of the longest path are nothing but
leaves. Hence, all we need to do is figure out is for which set of
leaves would the path be maximum..
[ Special Case : it need to be always leaves. For ex- consider a
binary tree having all right children set to NULL. Here, the 2 nodes
comprising the longest path would be the ("only")leaf node and the
root node. ]
Pseudocode:
---------------------
*mPathLeftNode= NULL;
*mPathRightNode = NULL;
*maxHeightLeafNode = NULL;
*maxPathLength = 0;
// returns the height of the tree..
int findMPath(node * root, node **mPathLeftNode, node
**mPathRightNode, int *maxPathLength, node **maxHeightLeafNode)
{
int leftHeight =0, rightHeight=0;
node *maxHeightLTLeafNode = NULL;
node *maxHeightRTLeafNode = NULL;
if( !root ) return 0;
leftHeight = findMPath(root-> left, mPathLeftNode,
mPathRightNode, maxPathLength, &maxHeightLTLeafNode);
rightHeight = findMPath(root-> right, mPathLeftNode,
mPathRightNode, maxPathLength, &maxHeightRTLeafNode);
if( ! leftHeight)
maxHeightLTLeafNode = root;
if( ! rightHeight)
maxHeightRTLeafNode = root;
if( *maxPathLength < 1 + leftHeight + rightHeight)
{
*maxPathLength = 1 + leftHeight + rightHeight;
*mPathLeftNode = maxHeightLTLeafNode;
*mPathRightNode = maxHeightRTLeafNode;
}
*maxHeightLeafNode = (leftHeight >= rightHeight ?
maxHeightLTLeafNode : maxHeightRTLeafNode);
return 1 + (leftHeight >= rightHeight ? leftHeight :
rightHeight);
}
On Mar 25, 10:45 pm, Amol Sharma <[email protected]> wrote:
> @kartikeyan : +1
>
> yes...bfs/dfs from the leave node will work.
> --
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
> <http://gplus.to/amolsharma99>
> <http://twitter.com/amolsharma99><http://in.linkedin.com/pub/amol-sharma/21/79b/507><http://www.simplyamol.blogspot.com/>
>
> On Sun, Mar 25, 2012 at 11:07 PM, karthikeyan muthu <
>
>
>
>
>
>
>
> [email protected]> wrote:
> > 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 ..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
