Lowest Common Ancestor of a Binary Search Tree
MediumTrees
You get the root of a binary search tree, where every value in a node’s left subtree is smaller than the node and every value in its right subtree is larger. You also get two different nodes of the tree, p and q.
Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as being in its own subtree, so p itself can be the answer.
On this page the tree is written in level order, top to bottom and left to right, with null where a child is missing, and p and q are written as their values. The tests find those nodes in the tree, pass the nodes to you, and read the value of the node you return.
Examples
Input: root = [40, 20, 60, 10, 30, null, 70, null, 15, 25], p = 15, q = 25 Output: 20
15 sits left of 20 and 25 right of it, so their paths split at 20.
Input: root = [40, 20, 60, 10, 30, null, 70, null, 15, 25], p = 60, q = 70 Output: 60
70 is below 60, and 60 counts as its own ancestor.
Constraints
- The tree has 2 to 10⁵ nodes.
-10⁹ ≤ node.val ≤ 10⁹, and no two nodes share a value.pandqare different nodes, and both are in the tree.
Stuck?
Hint 1
In a search tree the values tell you where to look: a value smaller than a node lives to its left, a larger one to its right.
Hint 2
Start at the root. If p and q are both smaller, move left; if both are larger, move right. Otherwise their paths split here, or one of them is this node, so this is the answer.
The idea
In a search tree, a value smaller than a node can only be in its left subtree, and a larger one only in its right. Walk down from the root while p and q are on the same side. The first node where they are not, because they split there or because one of them is that node, is the answer.
Time O(h) for a tree of height hExtra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Start at the root, which is an ancestor of both. Each move goes one level down, so the walk takes O(h) steps and needs no stack.
function lowestCommonAncestor(root, p, q) { let node = root; while (node) { if (p.val < node.val && q.val < node.val) node = node.left; else if (p.val > node.val && q.val > node.val) node = node.right; else return node; } return null;}The trap
Using <= and >= looks like tidying up the edges, but it walks past the answer when one of the two nodes is an ancestor of the other. At that node one value equals node.val, so the walk moves down anyway and ends at the wrong node or at null. When the two nodes sit on different sides of the answer, the equal case never comes up, so those inputs pass.
function lowestCommonAncestor(root, p, q) { let node = root; while (node) { // <= and >= walk past a node that is p or q itself if (p.val <= node.val && q.val <= node.val) node = node.left; else if (p.val >= node.val && q.val >= node.val) node = node.right; else return node; } return null;}