We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
Given a binary search tree and two values p and q that both exist in it, return the value of their lowest common ancestor - the deepest node having both as descendants.
A node is allowed to be a descendant of itself.
The tree is given as a level-order array with explicit nulls, where the children of index i sit at 2i + 1 and 2i + 2. An empty array is an empty tree.
An easy trees problem, graded against 6 test cases (3 of them hidden).
Recursive traversal of binary trees and BSTs - depth, validation, and path problems.
Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.
More Trees problems →The general-tree version of this problem requires searching both subtrees and combining results. A BST makes it almost trivial, because comparing values tells you where each target lives without looking.
Descend from the root. While both targets are less than the current value, both are in the left subtree, so move left; while both are greater, move right. The first node where they diverge - one on each side, or one equal to the current node - is the lowest common ancestor, because any deeper node would have both targets on the same side of it and could not be an ancestor of both.
That "or one equals the current node" clause is what implements the rule that a node counts as its own descendant, and it is the case people miss.
Since the walk never backtracks, this needs no recursion and no stack - a simple loop in O(1) space. It runs in O(h): O(log n) on a balanced tree, O(n) on a degenerate one.
The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.
Read off this problem's own test suite, so these are the cases a submission actually has to survive.
These apply to the pattern as a whole, not just this problem.