Lowest Common Ancestor of a Binary Search Tree
The problem
In a BST with distinct values, find the lowest node whose subtree contains two given nodes p and q. A node may be its own ancestor; both targets exist.
Example
In a BST rooted at 6, targets 2 and 8 have lowest common ancestor 6.
Need a hint?
Use the ordering rule before exploring any children.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
If both target values are smaller than the current node, move left. If both are larger, move right. Otherwise the targets split here, or the current node equals a target, so return it. No full traversal is needed.
Complexity
O(h) time and O(1) extra space with iteration.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.