Solving Lowest Common Ancestor in a Binary Search Tree

Above is a binary search tree. We start with a head node, in this situation, the head node is 8. Each node that is added afterwards will either go to the left or the right of the 8, depending on whether it is larger or smaller. You can see how the tree breaks down.

The question we will be answering now is finding the lowest shared ancestor between two nodes. Some examples with this image would be: 1 & 6 have the lowest common ancestor of 3 and 4 & 7 having a lowest common ancestor of 6.

We'll be solving this with a recursive solution. Although recursion may seem intimidating, once you see the solution, it will make sense and seem simple.

The arguments being passed in are the head node of the tree, num1, and num2. If both numbers are larger than the value of the head node, then we will recursively call the function with node.right being passed in now instead of the head. If both numbers are smaller, then we will recursively call the function with node.left as the node. If both the numbers are on each side of the node, then we know we have reached the lease common ancestor.

So in our example, we pass in head node with value of 8, the number 4, and number 7. So our first time we call findLCA, we will check where 4 & 7 compare to 8. Both numbers are less than 8, so we will recursively call findLCA with the arguments node.left, which has a value of 3, 4, and 7. We'll do another check and see that 4 & 7 are both larger than 3, so we will do another recursive call of findLCA. This time it will be called with node.right, which is now 6, and our two original numbers 4 and 7. In this function call, we will compare 4 & 7 to 6. Well now the numbers fall on either side of 6. So we know that we can return 6 at this point.

Finally, we will see that our function returns 6.