Find the Meeting Point of Two Keys in a Search Tree

Easy15–20 min

Topics

Binary Search TreeBSTAncestorsIteration

Companies

AmazonMicrosoftGoogleFacebookLinkedIn

You are given the root of a binary search tree with distinct values and two values p and q that both appear in the tree. Return the value of the lowest node that has both the p-node and the q-node in its subtree; a node counts as being inside its own subtree, so if one of the two nodes is an ancestor of the other, that ancestor is the answer.

The method for general binary trees works here too, but the ordering of a search tree lets you find the answer with a single downward walk, since the keys tell you which side each of them is on.

Test Case 1:

Input:root = [50, 25, 75, 10, 35, 60, 90, 5, 15, 30, 40], p = 15, q = 40

Output:25

Explanation:15 lies in the left subtree of 25 (via 10) and 40 in its right subtree (via 35), so 25 is where their paths split.

Test Case 2:

Input:root = [50, 25, 75, 10, 35, 60, 90, 5, 15, 30, 40], p = 30, q = 35

Output:35

Explanation:30 is a child of 35, so the lowest node above both is 35 itself.

Test Case 3:

Input:root = [50, 25, 75, 10, 35, 60, 90, 5, 15, 30, 40], p = 5, q = 90

Output:50

Explanation:One key is below each child of the root, so the root is the answer.

Constraints

◆2 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node
◆p and q are values that both exist in the tree (they may be equal to each other)
◆Return the value of the lowest node that has both the p-node and the q-node in its subtree (a node counts as being in its own subtree, so if one is an ancestor of the other, the answer is that ancestor)

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Treat It as an Ordinary Tree and Search Both Sides

Brute

Ignore the ordering and use the general method: a helper returns a node as soon as it is p or q, and otherwise asks both subtrees. If both report something, this node is the meeting point; if only one does, pass its answer up. This is correct for any binary tree but it may visit every node — O(n) time, O(h) recursion space — and it never uses the search-tree property.

TimeO(n)

SpaceO(h)

Java

Try it out

class Solution {
    public int lowestCommonInBst(TreeNode root, int p, int q) {
        return find(root, p, q).val;
    }

    private TreeNode find(TreeNode node, int p, int q) {
        if (node == null || node.val == p || node.val == q) return node;
        TreeNode left = find(node.left, p, q);
        TreeNode right = find(node.right, p, q);
        if (left != null && right != null) return node;
        return left != null ? left : right;
    }
}

Optimal — Walk Down Until the Two Keys Go Different Ways

Optimal

In a search tree the ordering tells where each key is. Starting at the root: if BOTH keys are smaller than the current node they are both in the left subtree, so move left; if BOTH are larger, move right. The first node at which they are NOT on the same side — one is smaller and the other larger, or one of them equals the node — is where their paths separate, and that node is the lowest one above both. It is found with a single downward walk: O(h) time and O(1) space.

TimeO(h)

SpaceO(1)