They Indirectly Asked To Fine Lowest Comman Ancestor in BST... so
The main idea of the solution is — While traversing BST from top to
bottom, the first node y we encounter with value between x and z
so if if Y lies between X and Z it means Y is LCA of X & Z-- where
X<Z also true
if above condition falls then repeat with left sub-tree e.g if Y is
greater then both x and z then traverse recursively for left sub-tree.
e.g y>x && y>z
else recurse for right subtree. y < x && y <z
here is function
int LCA(struct node* root, int x, int z)
{
if(root == NULL || root->data == z|| root->data == z)
return -1;
if((root->right != NULL) &&
(root->right->data == x || root->right->data == z))
return root->data;
if((root->left != NULL) &&
(root->left->data ==x || root->left->data == z))
return root->data;
if(root->data > x && root->data < z)
return root->data;
if(root->data > x && root->data > z)
return leastCommanAncestor(root->left, x,z);
if(root->data < x && root->data < z)
return leastCommanAncestor(root->right, x,z);
}
Thanks & Regards
Shashank
--
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.
