@above:
Special Case : it need *not* be always leaves
On Mar 26, 2:42 am, Lucifer <sourabhd2...@gmail.com> wrote:
> 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 <amolsharm...@gmail.com> 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 <
>
> > keyankarthi1...@gmail.com> 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 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.
