Sweaty Imposter

Lowest Common Ancestor of a BST

MediumTree DFSBlind 75MidOpen on LeetCodeUpdated

You're given the root of a binary search tree (smaller values in every left subtree, larger in every right) and two different nodes p and q that are both in it. Return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as part of its own subtree, so if p is above q, the answer is p. Example trees are listed row by row from the top, each row left to right, with null where a child is missing; p and q are given by value.

Examples

root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 returns 6

628047935
2 and 8 sit on opposite sides of 6.

2 is in the root's left subtree and 8 is in its right subtree, so their paths from the root split right away at 6. No deeper node has both below it.

root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 returns 2

628047935
4 lies below 2, so 2 is the answer.

4 is in the subtree of 2, and a node counts as part of its own subtree, so 2 itself is the deepest node containing both.

Constraints

  • 2 <= number of nodes <= 10^5
  • All node values are unique.

Hints

Hint 1

How does the BST ordering tell you whether two targets are on the same side of a node?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Start at the root and let the ordering steer. If p and q are both smaller than the current node, both lie in its left subtree, so move left; if both are larger, move right. Otherwise they fall on different sides, or one of them is the current node, so this is where their paths split and it is the answer. O(h) time, where h is the tree height, and O(1) space because the walk is a loop.

Time

O(h)

Space

O(1)

Pitfall

Only stopping when p and q fall strictly on opposite sides. When the current node is p or q itself, as with p = 2, q = 4, it is the answer, so the stopping case must include equality.

Solutions

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) root = root.left;
            else if (p.val > root.val && q.val > root.val) root = root.right;
            else return root;
        }
        return null;
    }
}
Drill This