Lowest Common Ancestor of a Binary Search Tree

Medium
1915.

Lowest Common Ancestor of a Binary Search Tree

Lowest Common Ancestor of a Binary Search Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon, Microsoft, Meta and LinkedIn interviews.

You are given the root of a binary search tree with distinct values and the values p and q of two different nodes in it.

The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree — where a node counts as being in its own subtree, so a node can be the ancestor of itself. Return the value of the lowest common ancestor of the nodes holding p and q.

Example 1

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output
6
Explanation
2 is in the root's left subtree and 8 in its right, so they part ways at the root 6.

Example 2

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output
2
Explanation
4 lies below 2, and a node counts as its own descendant, so the answer is 2.

Example 3

Input
root = [2,1], p = 2, q = 1
Output
2
Explanation
The root is an ancestor of 1 and of itself.

Constraints

  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • all node values are distinct
  • root is a valid binary search tree
  • p != q
  • p and q both exist in the tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} p
 * @param {number} q
 * @return {number}
 */
var lowestCommonAncestor = function(root, p, q) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lowest Common Ancestor of a Binary Search Tree — Solution

Lowest Common Ancestor of a Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Lowest Common Ancestor of a Binary Search Tree is a medium coding problem on depth-first search, binary search and trees, asked in Amazon, Microsoft, Meta and LinkedIn interviews.

Problem statement

You are given the root of a binary search tree with distinct values and the values p and q of two different nodes in it.

The lowest common ancestor of two nodes is the deepest node that has both of them in its subtree — where a node counts as being in its own subtree, so a node can be the ancestor of itself. Return the value of the lowest common ancestor of the nodes holding p and q.

Example 1

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the root's left subtree and 8 in its right, so they part ways at the root 6.

Example 2

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: 4 lies below 2, and a node counts as its own descendant, so the answer is 2.

Example 3

Input: root = [2,1], p = 2, q = 1
Output: 2
Explanation: The root is an ancestor of 1 and of itself.

Constraints

  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • all node values are distinct
  • root is a valid binary search tree
  • p != q
  • p and q both exist in the tree

Hints for Lowest Common Ancestor of a Binary Search Tree

  1. Hint 1

    Compare p and q with the root's value: when both are smaller, both nodes are in the left subtree; when both are larger, both are in the right subtree.

  2. Hint 2

    Keep moving down while p and q are on the same side of the current node.

  3. Hint 3

    The first node where they split — or where one of them equals the node — is the answer.

How to solve Lowest Common Ancestor of a Binary Search Tree

The ordering tells you which side each value is on, so walk down from the root while p and q lie on the same side; the node where they separate is their lowest common ancestor.

Approach

  1. Start at the root.
  2. If p and q are both smaller than the node's value, move to the left child.
  3. If both are larger, move to the right child.
  4. Otherwise (they are on different sides, or one equals the node) return the node's value.

Why it works

While both values lie on the same side of a node, both nodes are in that child's subtree, so the child is a common ancestor deeper than the current one. At the first node where they do not, one is in its left subtree (or is the node) and the other in its right subtree (or is the node), so no child contains both — this node is the deepest common ancestor.

Complexity

  • Time — O(h), h the height of the tree
  • Space — O(1)

Pitfalls

  • A node is its own descendant: when p is the current node, it is the answer even though q is below it.
  • The general binary-tree method also works but ignores the ordering that makes this a single walk.

Reference solution

Python

from typing import Optional

def lowestCommonAncestor(root: Optional[TreeNode], p: int, q: int) -> int:
    node = root
    while node:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
    return -1

Java

public static int lowestCommonAncestor(TreeNode root, int p, int q) {
    TreeNode node = root;
    while (node != null) {
        if (p < node.val && q < node.val) node = node.left;
        else if (p > node.val && q > node.val) node = node.right;
        else return node.val;
    }
    return -1;
}

C++

int lowestCommonAncestor(TreeNode* root, int p, int q) {
    TreeNode* node = root;
    while (node) {
        if (p < node->val && q < node->val) node = node->left;
        else if (p > node->val && q > node->val) node = node->right;
        else return node->val;
    }
    return -1;
}

JavaScript

var lowestCommonAncestor = function(root, p, q) {
    var node = root;
    while (node !== null) {
        if (p < node.val && q < node.val) node = node.left;
        else if (p > node.val && q > node.val) node = node.right;
        else return node.val;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Search