PROBLEM DESCRIPTION
Given a Binary Search Tree (with all values unique) and two node values n1 and n2 (n1!=n2). Find the Lowest Common Ancestors of the two nodes in the BST.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class BST
{
// LCA: lowest node in the tree that has both n1 and n2 as descendants.
Node LCA(Node root, int n1, int n2)
{
// If the root is null, there is no tree, so return null.
if(root == null)
return null;
// If both n1 and n2 are smaller than the root's data, the LCA must be in the left subtree.
if(n1 < root.data && n2 < root.data)
return LCA(root.left, n1, n2);
// If both n1 and n2 are greater than the root's data, the LCA must be in the right subtree.
else if(n1 > root.data && n2 > root.data)
return LCA(root.right, n1, n2);
// If one of n1 or n2 is on one side of the root and the other is on the other side,
// or if one of them matches the root itself, the current node is the LCA.
else
return root;
}
}