Find the lowest common ancestor of two binary tree nodes

"Find the lowest common ancestor of two nodes in a binary tree." This problem, also known as Lowest Common Ancestor of a Binary Tree on LeetCode, is a staple of technical interviews at companies like Facebook, Amazon, and Microsoft. It tests your ability to think recursively about tree structure and combine information flowing up from subtrees. If you can solve this cleanly, you understand how to propagate state through a DFS traversal.

TL;DR

Run a depth-first search that returns a boolean from each subtree. At each node, check three conditions: does the left subtree contain a target, does the right subtree contain a target, and is the current node itself a target. When two of these three conditions are true, you have found the LCA. Store the result in a mutable container and return it after the traversal completes.

Why This Problem Matters

The lowest common ancestor problem sits at the intersection of recursion and tree traversal. It forces you to think about what information each recursive call should return and how parent nodes combine results from their children. This pattern of "gather information from subtrees and make a decision at the current node" appears in dozens of other tree problems, from diameter calculation to path sum queries. Nail this one, and you have a template for a whole class of problems.

Understanding the Problem

Given the root of a binary tree and two distinct integer values representing nodes in the tree, return the value of their lowest common ancestor. The LCA is the deepest node that has both targets as descendants, and a node can be its own descendant.

Consider this tree:

Tree: 1 2 3 4 5 # #

         1
        / \
       2   3
      / \
     4   5

lca(root, 4, 5) -> 2
lca(root, 5, 3) -> 1
lca(root, 4, 3) -> 1
lca(root, 4, 2) -> 2

Edge Cases

1. One target is an ancestor of the other: lca(root, 4, 2) returns 2 because node 2 is an ancestor of node 4, and a node counts as its own descendant.
2. Both targets are in the same subtree: lca(root, 4, 5) returns 2 because both targets are in the left subtree of 1.
3. Targets are in different subtrees: lca(root, 5, 3) returns 1 because node 5 is in the left subtree and node 3 is in the right subtree of the root.

Solution Approach

The key insight is that we can determine the LCA by asking each subtree a simple yes-or-no question: "Do you contain one of the target nodes?" A recursive DFS naturally answers this question.

At every node, we track three boolean signals:

• left - does the left subtree contain a target?
• right - does the right subtree contain a target?
• mid - is the current node itself one of the targets?

When exactly two of these three signals are true, we have found the LCA. Here is why this works:

• If left && right: One target is in the left subtree and the other is in the right. The current node is the deepest point connecting both.
• If left && mid or right && mid: The current node is one target and the other target is in one of its subtrees. The current node is the LCA because a node is its own descendant.

The function returns left || right || mid to propagate upward whether this subtree contains at least one target.

Walking Through lca(root, 4, 5)

Let's trace the DFS to see how the algorithm identifies node 2 as the LCA:

The recursion bottoms out at leaves and null children, then results bubble up. When search(2) gets left=true from node 4 and right=true from node 5, two conditions are satisfied, so node 2 is the LCA.

lca(root, 5, 3) = 1

When targets span both subtrees, the root becomes the LCA:

Node 5 is in the left subtree and node 3 is in the right subtree. The only place they converge is at node 1.

lca(root, 4, 2) = 2

When one target is an ancestor of the other:

At node 2, mid is true (node 2 is a target) and left is true (node 4 is in the left subtree). Two conditions are satisfied, so node 2 is the LCA.

A Larger Tree

Here is a more complex example with a deeper tree:

For lca(root, 2, 5), node 2 is deep in the left subtree under node 3, and node 5 is a right child of node 4. They converge at node 4, which is the LCA.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int lca(TreeNode root, int n1, int n2) {
    int[] lcaData = new int[1];
    search(root, n1, n2, lcaData);
    return lcaData[0];
  }

  private boolean search(TreeNode node, int n1, int n2, int[] lcaData) {
    if (node == null) return false;

    boolean left = search(node.left, n1, n2, lcaData);
    boolean right = search(node.right, n1, n2, lcaData);
    boolean mid = node.data == n1 || node.data == n2;

    if ((left && right) || (left && mid) || (right && mid))
      lcaData[0] = node.data;

    return left || right || mid;
  }
}

Let's break down how this works:

1. Placeholder array: We use int[] lcaData as a mutable container to store the LCA result. The helper method already returns a boolean, so we need a side channel for the LCA value.

2. Base case: If the node is null, return false. This subtree contains neither target.

3. Recursive calls: Explore left and right subtrees. Each returns true if its subtree contains at least one target.

4. Mid check: Determine whether the current node is itself one of the targets.

5. LCA detection: If any two of the three signals (left, right, mid) are true, this node is the LCA. Store its value.

6. Return: Return true if this subtree contains at least one target node, enabling ancestor nodes to continue the search.

Complexity Analysis

Time: O(n). Every node is visited at most once during the DFS traversal. There is no repeated work since each subtree is explored exactly once.

Space: O(n). The recursion stack can grow up to n frames deep in the worst case (a completely skewed tree). For a balanced binary tree, the space is O(log n). The placeholder array uses O(1) additional space.

Common Pitfalls

1. Returning early after finding one target: A common mistake is to return immediately when you find one target. You need to keep searching because the other target might be in a different subtree, and you need both signals to identify the LCA.

2. Forgetting the "node is its own descendant" rule: The problem states that a node can be a descendant of itself. This is why we check the mid condition. Without it, lca(root, 4, 2) would incorrectly return 1 instead of 2.

3. Using a class-level variable instead of a parameter: While a class field works, passing a mutable container keeps the solution thread-safe and avoids accidental state from previous calls. In an interview, the parameter approach is cleaner.

4. Confusing this with a BST problem: The BST approach of comparing values to decide left vs. right does not work for a general binary tree. You must explore both subtrees unconditionally.

Interview Tips

When presenting this solution:

• Start by explaining the recursive insight: each subtree reports whether it contains a target, and the LCA is where two signals converge.
• Draw the tree and trace through at least one example. Show how the booleans bubble up and where the LCA condition triggers.
• Mention the time and space complexity upfront. O(n) time is optimal since you might need to visit every node.
• If the interviewer asks about BSTs, mention that the ordering property allows an O(h) solution without full DFS.
• Point out that the placeholder array approach keeps the helper's return type clean. You could alternatively use a wrapper class or return a tuple, but the array is simplest in Java.

Key Takeaways

• The LCA is the deepest node where two target nodes converge. It is identified by checking three boolean conditions: left subtree contains a target, right subtree contains a target, and the current node is a target.
• A recursive DFS naturally solves this by propagating boolean signals upward. When two of the three conditions are true at a node, that node is the LCA.
• Time complexity is O(n) and space complexity is O(n) in the worst case, O(log n) for balanced trees.
• A node can be its own descendant, which means the mid flag is essential for correctness.
• This "gather and combine" pattern at tree nodes is foundational. Once you understand it, you can apply it to tree diameter, maximum path sum, and many other problems.

Practice and Related Problems

Once you have the LCA pattern down, try these related problems:

• LCA in a Binary Search Tree (optimize using BST ordering for O(h) time)
• Diameter of a Binary Tree (similar "combine left and right subtree results" pattern)
• Path Sum (DFS with state propagation through recursion)

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize tree traversal patterns rather than just memorizing solutions. Building strong recursive thinking here pays dividends across your entire interview preparation.

Solutions in Other Languages

Python

class Solution:
    def lca(self, root: TreeNode, n1: int, n2: int) -> int:
        lca_data = []
        self.search(root, n1, n2, lca_data)
        return lca_data[0]

    def search(self, node: TreeNode, n1: int, n2: int, lca_data) -> bool:
        if node is None:
            return False
        left = self.search(node.left, n1, n2, lca_data)
        right = self.search(node.right, n1, n2, lca_data)
        mid = (node.data == n1) or (node.data == n2)
        if (left and right) or (left and mid) or (right and mid):
            lca_data.append(node.data)
        return left or right or mid

JavaScript

class Solution {
  lca(root, n1, n2) {
    const lcaData = [];
    this.search(root, n1, n2, lcaData);
    return lcaData[0];
  }

  search(node, n1, n2, lcaData) {
    if (node === null) return false;
    const left = this.search(node.left, n1, n2, lcaData);
    const right = this.search(node.right, n1, n2, lcaData);
    const mid = node.data === n1 || node.data === n2;
    if ((left && right) || (left && mid) || (right && mid))
      lcaData[0] = node.data;
    return left || right || mid;
  }
}

TypeScript

class Solution {
  lca(root: TreeNode | null, n1: number, n2: number): number {
    const lcaData: number[] = [];
    this.search(root, n1, n2, lcaData);
    return lcaData[0];
  }

  search(node: TreeNode | null, n1: number, n2: number, lcaData: number[]): boolean {
    if (node === null) return false;
    const left = this.search(node.left, n1, n2, lcaData);
    const right = this.search(node.right, n1, n2, lcaData);
    const mid = node.data === n1 || node.data === n2;
    if ((left && right) || (left && mid) || (right && mid))
      lcaData[0] = node.data;
    return left || right || mid;
  }
}

C++

class Solution {
public:
  int lca(TreeNode *root, int n1, int n2) {
    int lca = 0;
    search(root, n1, n2, &lca);
    return lca;
  }

private:
  bool search(TreeNode *node, int n1, int n2, int *lcaRef) {
    if (node == nullptr)
      return false;
    bool left = search(node->left, n1, n2, lcaRef);
    bool right = search(node->right, n1, n2, lcaRef);
    bool mid = node->data == n1 || node->data == n2;
    if ((left && right) || (left && mid) || (right && mid))
      *lcaRef = node->data;
    return left || right || mid;
  }
};

Go

package solution

func (s *Solution) Lca(root *TreeNode, n1 int, n2 int) int {
    lca := 0
    search(root, n1, n2, &lca)
    return lca
}

func search(node *TreeNode, n1 int, n2 int, lcaRef *int) bool {
    if node == nil {
        return false
    }
    left := search(node.Left, n1, n2, lcaRef)
    right := search(node.Right, n1, n2, lcaRef)
    mid := node.Data == n1 || node.Data == n2
    if (left && right) || (left && mid) || (right && mid) {
        *lcaRef = node.Data
    }
    return left || right || mid
}

Scala

class Solution {
  def lca(root: TreeNode, n1: Int, n2: Int): Int = {
    val lcaData = new Array[Int](1)
    search(root, n1, n2, lcaData)
    lcaData(0)
  }

  private def search(node: TreeNode, n1: Int, n2: Int, lcaData: Array[Int]): Boolean = {
    if (node == null) return false
    val left = search(node.left, n1, n2, lcaData)
    val right = search(node.right, n1, n2, lcaData)
    val mid = (node.data == n1) || (node.data == n2)
    if ((left && right) || (left && mid) || (right && mid)) lcaData(0) = node.data
    left || right || mid
  }
}

Kotlin

class Solution {
    fun lca(root: TreeNode?, n1: Int, n2: Int): Int {
        val lcaData = IntArray(1)
        search(root, n1, n2, lcaData)
        return lcaData[0]
    }

    private fun search(node: TreeNode?, n1: Int, n2: Int, lcaData: IntArray): Boolean {
        if (node == null) return false
        val left = search(node.left, n1, n2, lcaData)
        val right = search(node.right, n1, n2, lcaData)
        val mid = node.data == n1 || node.data == n2
        if ((left && right) || (left && mid) || (right && mid))
            lcaData[0] = node.data
        return left || right || mid
    }
}

Swift

class Solution {
    func lca(_ root: TreeNode?, _ n1: Int, _ n2: Int) -> Int {
        var lcaData = [0]
        search(root, n1, n2, &lcaData)
        return lcaData[0]
    }

    @discardableResult
    private func search(_ node: TreeNode?, _ n1: Int, _ n2: Int, _ lcaData: inout [Int]) -> Bool {
        if node == nil { return false }
        let left = search(node!.left, n1, n2, &lcaData)
        let right = search(node!.right, n1, n2, &lcaData)
        let mid = node!.data == n1 || node!.data == n2
        if (left && right) || (left && mid) || (right && mid) {
            lcaData[0] = node!.data
        }
        return left || right || mid
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn lca(&self, root: Option<Box<TreeNode>>, n1: i32, n2: i32) -> i32 {
        let mut lca_data = 0;
        Self::search(&root, n1, n2, &mut lca_data);
        lca_data
    }

    fn search(node: &Option<Box<TreeNode>>, n1: i32, n2: i32, lca_data: &mut i32) -> bool {
        match node {
            None => false,
            Some(n) => {
                let left = Self::search(&n.left, n1, n2, lca_data);
                let right = Self::search(&n.right, n1, n2, lca_data);
                let mid = n.data == n1 || n.data == n2;
                if (left && right) || (left && mid) || (right && mid) {
                    *lca_data = n.data;
                }
                left || right || mid
            }
        }
    }
}

C#

public class Solution {
    public int Lca(TreeNode? root, int n1, int n2) {
        int[] lcaData = new int[1];
        Search(root, n1, n2, lcaData);
        return lcaData[0];
    }

    private bool Search(TreeNode? node, int n1, int n2, int[] lcaData) {
        if (node == null) return false;
        bool left = Search(node.left, n1, n2, lcaData);
        bool right = Search(node.right, n1, n2, lcaData);
        bool mid = node.data == n1 || node.data == n2;
        if ((left && right) || (left && mid) || (right && mid))
            lcaData[0] = node.data;
        return left || right || mid;
    }
}

Dart

class Solution {
  int lca(TreeNode? root, int n1, int n2) {
    List<int> lcaData = [0];
    _search(root, n1, n2, lcaData);
    return lcaData[0];
  }

  bool _search(TreeNode? node, int n1, int n2, List<int> lcaData) {
    if (node == null) return false;
    bool left = _search(node.left, n1, n2, lcaData);
    bool right = _search(node.right, n1, n2, lcaData);
    bool mid = node.data == n1 || node.data == n2;
    if ((left && right) || (left && mid) || (right && mid))
      lcaData[0] = node.data;
    return left || right || mid;
  }
}

PHP

class Solution {
    public function lca(?TreeNode $root, int $n1, int $n2): int {
        $lcaData = [0];
        $this->search($root, $n1, $n2, $lcaData);
        return $lcaData[0];
    }

    private function search(?TreeNode $node, int $n1, int $n2, array &$lcaData): bool {
        if ($node === null) return false;
        $left = $this->search($node->left, $n1, $n2, $lcaData);
        $right = $this->search($node->right, $n1, $n2, $lcaData);
        $mid = $node->data === $n1 || $node->data === $n2;
        if (($left && $right) || ($left && $mid) || ($right && $mid))
            $lcaData[0] = $node->data;
        return $left || $right || $mid;
    }
}

Ruby

class Solution
  def lca(root, n1, n2)
    lca_data = [0]
    search(root, n1, n2, lca_data)
    lca_data[0]
  end

  def search(node, n1, n2, lca_data)
    return false if node.nil?
    left = search(node.left, n1, n2, lca_data)
    right = search(node.right, n1, n2, lca_data)
    mid = node.data == n1 || node.data == n2
    lca_data[0] = node.data if (left && right) || (left && mid) || (right && mid)
    left || right || mid
  end
end