I know this is not a BST , in BST you do not have to inorder traversal it is
even shorter. You start from root and first instance when node1 <
currentNode < node 2 (or vice versa)you are done .
In case of normal binary tree. you just need to traverse till node1 and then
similarly for node2 . Now
depending upon the situation if you have to find the youngest ancestor
once then what rahul singh can be done
if the situation is you have mutliple query then do it in the following way
preprocessing : make a reversed tree eg
ABC
/ \
@Rahul,
The Tree is not Binary "Search" Tree.
Anurag Sharma
http://anuragsharma-sun.blogspot.com/
On Thu, Apr 8, 2010 at 6:52 PM, Rahul Singh wrote:
> Perform inorder traverse for both the node. match element by element the 2
> strings and when first time the string deviates thats Lowest commo
This will works well to find common ancestor
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
Perform inorder traverse for both the node. match element by element the 2
strings and when first time the string deviates thats Lowest common
ancestor.
-rahul
On Thu, Apr 8, 2010 at 6:21 PM, Anurag Sharma wrote:
> @Dave,
> Thanks for pointing out the limitation in my algorithm. I myself realized
@Dave,
Thanks for pointing out the limitation in my algorithm. I myself realized
the same mistake after I posted the algorithm. You are right, we should
additionally check the presence of A and B on the either side. It will add
few extra conditions to the algorithm. I will soon update the same on m
@Anurag.
I like your algorithm, but observe some deficiencies...
A could be on the right subtree and B on the left, as well.
And what if B is a descendent of A. Should we consider A to be the
lowest common ancestor (i.e., is a node an ancestor of itself?), or is
the LCA the first ancestor of A?
