Lowest Common Ancestor in a BST
Given a Binary Search Tree and 2 nodes value n1 and n2, your task is to find the lowest common ancestor of the two nodes. Assume that n1 and n2 both existing node value of the tree.
Input BST: 8 / \ 4 10 / \ / \ 3 5 9 11 n1: 9 n2: 11 Output:10 n1: 4 n2: 10 Output:8
The key idea of the solution is while traversing BST from root to bottom, the first node that is encountered with a value between n1 and n2, i.e., n1<node->data<n2, is the Least Common Ancestor(LCA) of those two nodes having values n1, n2 respectively.
So, traverse the BST using pre-order traversal. If we find a node with value in between n1 and n2, the node is the LCA. If its (the currently processed node) value is greater than both n1 and n2, then the LCA lies in the left subtree of the currently processed node and if its (the currently processed node) value is smaller than both n1 and n2 then the LCA must be on the right subtree of the currently processed node.
Example with explanation: