Lowest Common Ancestor of a Binary Tree

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree (not necessarily a search tree) and two nodes p and q that are both in the tree. 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 lies below q, the answer is q itself.

In the tests, the tree is written as a level-order array where null marks a missing child, and p and q are given by their values (all values are distinct). Your function receives the actual node objects and must return a node; the judge checks the value of the node you return.

Example 1

Input: root = [7,3,12,1,5,9,15,null,null,4,6], p = 4, q = 9 Output: 7 Why: 4 sits under 3 on the left and 9 under 12 on the right, so they first meet at the root 7.

Example 2

Input: root = [7,3,12,1,5,9,15,null,null,4,6], p = 4, q = 6 Output: 5 Why: 4 and 6 are both children of 5.

Example 3

Input: root = [7,3,12,1,5,9,15,null,null,4,6], p = 3, q = 6 Output: 3 Why: 6 is a descendant of 3, so 3 is its own lowest common ancestor with 6.

Constraints

2 <= number of nodes <= 10⁵
-10⁹ <= Node.val <= 10⁹; all values are distinct
p and q are both in the tree (they may be the same node)

Pattern Path · Trees: DFS · problem 87 of 169

Ask each subtree a simple question: does it contain p or q?

Write a recursive function that returns p or q if it finds one in the subtree (or the answer, once known), and null otherwise. If the current node is p or q, return it right away.

If both the left and right recursive calls return something non-null, p and q are on different sides, so the current node is the answer. If only one side is non-null, pass that result up.

Target: O(n) time, O(h) for the recursion, h = tree height extra space.

Start simple

Record the root-to-node path for p and for q with two searches, then walk both paths together until they diverge: O(n) time but two passes and O(n) extra lists.

The key idea

Do a single post-order DFS where each call returns one of three things for its subtree: null (neither target found), a target node (one of them found), or the final answer.

If the current node is null, p or q, return it immediately.
Otherwise recurse into both children.
If both children report a node, p is in one subtree and q in the other, so this node is the deepest place where they meet: return it.
If only one side is non-null, return that side: it either holds one target that still needs its partner, or an answer found deeper down that should bubble up unchanged.

Why is returning early at p safe even when q is below p? Because then nothing else in the tree reports a node, so p bubbles up all the way to the root and is the correct answer. Every node is visited at most once.

Complexity

Time: O(n)
Space: O(h) for the recursion, h = tree height

Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root          # p and q are on different sides
        return left or right     # pass up whatever was found (or None)

JavaScript

var lowestCommonAncestor = function(root, p, q) {
  if (root === null || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root; // p and q are on different sides
  return left || right;           // pass up whatever was found (or null)
};

What the interviewer is checking

This tests whether you can design a recursive function whose return value carries just enough information upward, and reason about the case where one node is an ancestor of the other.

Mistakes to avoid

Using BST ordering (comparing values), which only works for search trees.
Not handling the case where one target is an ancestor of the other.
Comparing values instead of node identity when duplicates could exist (here they do not, but the habit matters).
Deep, skewed trees can overflow the recursion stack; an iterative parent-pointer approach avoids that.

Follow-ups to expect

What if the tree is a binary search tree? (Walk down using value comparisons.)
What if p or q might be missing from the tree? (Count found targets during DFS.)
Many queries on the same tree? (Binary lifting or Euler tour + RMQ.)

In real software

Version-control systems find the merge base of two branches as a lowest common ancestor, and DOM libraries, file systems and org charts use it to find the closest shared container or manager.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return null;
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (i < a.length) {
            TreeNode n = q.poll();
            if (a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

static TreeNode find(TreeNode n, int v) {
        if (n == null || n.val == v) return n;
        TreeNode l = find(n.left, v);
        return l != null ? l : find(n.right, v);
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{7, 3, 12, 1, 5, 9, 15, null, null, 4, 6});
        TreeNode ans = new Solution().lowestCommonAncestor(root, find(root, 4), find(root, 9));
        System.out.println(ans == null ? "null" : ans.val); // 7
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return nullptr;
    }
};

const int NUL = INT_MIN;  // marks a missing child

// Builds a tree from a level-order array (NUL = missing child).
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NUL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (a[i] != NUL) { n->left = new TreeNode(a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i] != NUL) { n->right = new TreeNode(a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

TreeNode* find(TreeNode* n, int v) {
    if (!n || n->val == v) return n;
    TreeNode* l = find(n->left, v);
    return l ? l : find(n->right, v);
}

int main() {
    TreeNode* root = build({7, 3, 12, 1, 5, 9, 15, NUL, NUL, 4, 6});
    TreeNode* ans = Solution().lowestCommonAncestor(root, find(root, 4), find(root, 9));
    cout << (ans ? to_string(ans->val) : "null") << endl;  // 7
}

Topics #087 #t-tree-dfs DFS Medium Practice Recursion Tree