Lowest Common Ancestor of a Binary Tree

Medium
1916.

Lowest Common Ancestor of a Binary Tree

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

You are given the root of a binary tree (not necessarily a search tree) whose node values are all distinct, 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 = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
Explanation
5 is in the root's left subtree and 1 in its right, so the deepest node holding both is the root 3.

Example 2

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

Example 3

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

Constraints

  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • all node values are distinct
  • 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 Tree — Problem & Solution

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

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

Problem statement

You are given the root of a binary tree (not necessarily a search tree) whose node values are all distinct, 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 = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: 5 is in the root's left subtree and 1 in its right, so the deepest node holding both is the root 3.

Example 2

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

Example 3

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

Constraints

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

Hints for Lowest Common Ancestor of a Binary Tree

  1. Hint 1

    Without an ordering you have to search both subtrees, so think recursively: what should a subtree report back to its parent?

  2. Hint 2

    Let a call return the node holding p or q if it finds one (stopping there), and null if its subtree holds neither.

  3. Hint 3

    If both the left and the right call come back non-null, the current node is where the two paths meet; otherwise pass up whichever side is non-null.

How to solve Lowest Common Ancestor of a Binary Tree

One post-order search answers "which of p and q are below here?" for every subtree; the first node that finds one target on each side — or is a target with the other below it — is the lowest common ancestor.

Approach

  1. Define find(node): if the node is null, or holds p or q, return the node.
  2. Otherwise call find on the left and right children.
  3. If both calls return a node, return the current node: p and q are on different sides.
  4. Otherwise return the non-null result (or null if both are null).
  5. The answer is the value of find(root).

Why it works

find returns null exactly when its subtree holds neither target, and otherwise a node inside it. A call stops at the first target it meets; if the other target is below it, that target is never reached, and that is correct because the stopping node is then the ancestor. If the targets are in different child subtrees, both children report back and the current node is the deepest node containing both. Because the targets exist and are distinct, these cases cover everything, and the result bubbles up unchanged to the root.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Stopping at a target is not a shortcut that loses the answer: if the other target is below it, this node is the ancestor.
  • This relies on both values being present; with a missing value the function would wrongly return the one it found.

Reference solution

Python

from typing import Optional

def lowestCommonAncestor(root: Optional[TreeNode], p: int, q: int) -> int:
    def find(node):
        if node is None or node.val == p or node.val == q:
            return node
        left = find(node.left)
        right = find(node.right)
        if left and right:
            return node
        return left if left else right

    return find(root).val

Java

public static int lowestCommonAncestor(TreeNode root, int p, int q) {
    return lcaFind(root, p, q).val;
}

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

C++

TreeNode* lcaFind(TreeNode* node, int p, int q);

int lowestCommonAncestor(TreeNode* root, int p, int q) {
    return lcaFind(root, p, q)->val;
}

TreeNode* lcaFind(TreeNode* node, int p, int q) {
    if (!node || node->val == p || node->val == q) return node;
    TreeNode* left = lcaFind(node->left, p, q);
    TreeNode* right = lcaFind(node->right, p, q);
    if (left && right) return node;
    return left ? left : right;
}

JavaScript

var lowestCommonAncestor = function(root, p, q) {
    return lcaFind(root, p, q).val;
};

var lcaFind = function(node, p, q) {
    if (node === null || node.val === p || node.val === q) return node;
    var left = lcaFind(node.left, p, q), right = lcaFind(node.right, p, q);
    if (left !== null && right !== null) return node;
    return left !== null ? left : right;
};

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 Trees and Tree Traversals