question
Given the values of two nodes in a binary search tree, write a function to find the lowest common ancestor. Assume both values exist in the tree.
ex. In the BST below the LCA of 15 and 25 is 20.
ex. In the BST below the LCA of 15 and 25 is 20.
Look out for special cases such as when the two input nodes belong to the same subtree and are at different levels.
The general algorithm for the solution involves traversing the BST top-to-bottom for the first node n, where n1 < n < n2 and inputs n1 < n2. This will find the lowest common ancestor to both nodes. While traversing, if any of the input nodes is a child of the current node, than we have reached the LCA. This can occur when both inputs are in the same subtree. In the tree above, with an input of 12 & 15, 20 should be returned because while traversing 12 is a child of 20. A recursive solution is below.
Thoughts or alternate solution? Let us know in the comments below!
findLCA(node root, int n1, int n2)
// If reach leaf node then LCA doesn't exist. If node equals n1/n2 then invalid input given. Ex. 9 & 20
if ( root == null || root.data == n1 || root.data == n2)
return -1;
if any input node is child of root node, root is the LCA.
//Ex. when we reach 20 with input of 12 & 15
return root.data;
if (root.data > n1 && root.data < n2)
return root.data;
if (root.data > n1 && root.data > n2)
return findLCA(root.left, n1, n2);
if (root.data < n1 && root.data < n2)
return findLCA(root.right, n1, n2);
From a helper function call findLCA with n1 < n2
Thoughts or alternate solution? Let us know in the comments below!