Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
/ \ / \
0 _4 7 9
For example, the lowest common ancestor (LCA) of nodes
6. Another example is LCA of nodes
2, since a node can be a descendant of itself according to the LCA definition.
Some thoughts on implementation -
The two nodes lie on either side of the LCA or the LCA is one of the node. So, start traversing from the root, and compare the value of the two nodes with the root. If both of the nodes lie either on left or right, go along that direction otherwise return root as the LCA.
Here’s an implementation of the same idea -