Rotate image (square matrix) by 90 deg
Tue, 06 May 2025
In a Binary Search Tree, you are given the values of two nodes. Write a code which will return the Lowest Common Ancestor of both the nodes.
For Example: If the given BST is as shown above and Nodes are 4 and 8,
The output should be: 5
4 and 8 has two common ancestors 5 and 10. But the lowest one is 5.Solution:
Lowest Common Ancestor will be the Node which is ancestor to the nodes and whose value lies between the two nodes.
For any two nodes in a BST, there is one and only one common ancestor whose value will be between the two nodes (i.e less than one and greater than the other).
Algorithm:FUNCTION FindCommonAncestor(Node * root, int a, int b)
IF (value_at_root < a AND value_at_root > b) OR (value_at_root < b AND value_at_root < a)
RETURN root
ELSE
IF (value_at_root < a AND value_at_root < b)
RETURN FindCommonAncestor(root->left_sub_tree, a, b)
ELSE
RETURN FindCommonAncestor(root->right_sub_tree, a, b)
Code:
/**
* Return the Least Common Ancestor (LCA) of Nodes with values a and b
*/
Node* commonAncestor(Node* root, int a, int b)
{
// case when LCA doesn't exist
if(root == NULL || root->data == a || root->data == b)
return NULL;
if( (root->data > a && root->data < b) || (root->data > b && root->data < a) )
return root;
// LCA will be on the LEFT sub-tree
if(root->data > a && root->data > b)
return commonAncestor(root->lptr, a, b);
// LCA will be on the RIGHT sub-tree
if(root->data < a && root->data < b)
return commonAncestor(root->rptr, a, b);
}
Tue, 06 May 2025
Tue, 06 May 2025
Tue, 06 May 2025
Leave a comment