Lowest Common Ancestor of a Binary Tree

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q in the tree.

The lowest common ancestor is the deepest node in the tree that is an ancestor of both p and q. A node can be an ancestor of itself.

What to notice first

• A node can be an ancestor of itself (if one of p or q is the ancestor of the other).
• The LCA is the deepest node that has both p and q in its subtree.
• Two different approaches: one uses recursion (DFS), the other uses parent pointers with hash set.

Examples

Input	p	q	Output	Explanation
[3,5,1,6,2,0,8,null,null,7,4]	5	1	3	3 is the LCA of 5 and 1
[3,5,1,6,2,0,8,null,null,7,4]	5	4	5	5 is the LCA of 5 and 4 (5 is ancestor of 4)
[1,2]	1	2	1	1 is the LCA of 1 and 2

Visualized Examples

Example 1:         3          LCA(5, 1) = 3
                 /   \
                5     1
               / \   / \
              6   2 0   8
                / \
               7   4

Example 2:  LCA(5, 4) = 5 (same tree, 5 is ancestor of 4)

Example 3:       1        LCA(1, 2) = 1 (1 is ancestor of itself and 2)
                  \
                   2

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All nodes have unique values.
• p and q will exist in the tree.

Real-World Applications

Where this pattern appears

• File system hierarchies — find the common parent directory of two files.
• Organizational structures — find the lowest common manager of two employees.
• Git commit history — find the merge base of two branches.
• DNA sequence analysis — find the common ancestor in evolutionary trees.
• Social networks — find the closest common connection between two users.

Complexity Comparison

Approach	Time	Space	Best When
DFS Recursive	O(n)	O(h)	Simple to implement; space is the call stack
Parent Pointers + Hash Set	O(n)	O(h)	If multiple LCA queries needed; explicit space usage

Where h = height (at most n)

Which approach should you learn first?

• Pick DFS Recursive if you want the simplest, most elegant solution that naturally leverages tree structure.
• Pick Parent Pointers + Hash Set if you want to understand how to track ancestry and use hash sets for quick lookups.

Simplest

DFS Recursive

O(n) time · O(h) space

Explicit Ancestry

Parent Pointers + Hash Set

O(n) time · O(h) space

Approach 1: DFS Recursive (Recommended)

★ Recommended

The key insight: the LCA of p and q is the deepest node where p and q are in different subtrees (or one is the node itself).

For each node, recursively search for p and q in its left and right subtrees:

• If both are found in different subtrees, this node is the LCA.
• If both are in one subtree, recurse into that subtree.
• If found in a subtree, return that node to propagate up.

⏱ Time O(n) Visit all nodes in worst case 💾 Space O(h) Recursion call stack

Step-by-step Example

Input: Tree with nodes [3,5,1,6,2,0,8], p = 5, q = 1

       3
      / \
     5   1
    / \ / \
   6  2 0  8

Node	Left Result	Right Result	Decision	Reason
6	null	null	null	Leaf, neither p nor q
2	null	null	null	Leaf, neither p nor q
5	p found	2 (not q)	return 5	Left subtree has p
0	null	null	null	Leaf, neither p nor q
8	null	null	null	Leaf, neither p nor q
1	0 (not p)	8 (not q)	return 1	This is q itself
3	5 (has p)	1 (has q)	return 3 ✓	Both in different subtrees

Animated walkthrough

How DFS finds the lowest common ancestor

Use Next or Autoplay to watch as recursion explores subtrees and identifies where p and q meet.

Back Autoplay Next Reset

Step 1 of 4

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function lca(root, p, q):
    if root is null:
        return null

    if root is p or root is q:
        return root

    left = lca(root.left, p, q)
    right = lca(root.right, p, q)

    if left is not null and right is not null:
        return root          // Both found in different subtrees

    return left if left is not null else right  // One subtree has both

Solution Code

Python

lowest_common_ancestor_of_a_binary_tree_dfs.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find the lowest common ancestor of two nodes in a binary tree using DFS.

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(h) where h is the height (call stack depth)
    """
    if root is None:
        return None

    # If either p or q is the current node, it's a potential LCA
    if root == p or root == q:
        return root

    # Search in left and right subtrees
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)

    # If both p and q are found in different subtrees, root is LCA
    if left is not None and right is not None:
        return root

    # If both are in one subtree, return that subtree's result
    return left if left is not None else right


# Test cases
if __name__ == "__main__":
    # Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    #       3
    #      / \
    #     5   1
    #    / \ / \
    #   6  2 0  8
    #     / \
    #    7   4
    root1 = TreeNode(3)
    root1.left = TreeNode(5)
    root1.right = TreeNode(1)
    root1.left.left = TreeNode(6)
    root1.left.right = TreeNode(2)
    root1.right.left = TreeNode(0)
    root1.right.right = TreeNode(8)
    root1.left.right.left = TreeNode(7)
    root1.left.right.right = TreeNode(4)

    p1 = root1.left  # Node 5
    q1 = root1.right  # Node 1
    result1 = lowestCommonAncestor(root1, p1, q1)
    print(f"LCA of {p1.val} and {q1.val}: {result1.val}")  # Expected: 3

    # Example 2: Same tree, p=5, q=4
    p2 = root1.left  # Node 5
    q2 = root1.left.right.right  # Node 4
    result2 = lowestCommonAncestor(root1, p2, q2)
    print(f"LCA of {p2.val} and {q2.val}: {result2.val}")  # Expected: 5

    # Example 3: [1,2]
    #     1
    #      \
    #       2
    root3 = TreeNode(1)
    root3.right = TreeNode(2)

    p3 = root3  # Node 1
    q3 = root3.right  # Node 2
    result3 = lowestCommonAncestor(root3, p3, q3)
    print(f"LCA of {p3.val} and {q3.val}: {result3.val}")  # Expected: 1

C++

lowest_common_ancestor_of_a_binary_tree_dfs.cpp

#include <iostream>
using namespace std;

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

class Solution {
public:
    /**
     * Find the lowest common ancestor using DFS recursion.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height (call stack depth)
     */
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) {
            return nullptr;
        }

        // If either p or q is the current node, it's a potential LCA
        if (root == p || root == q) {
            return root;
        }

        // Search in left and right subtrees
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        // If both p and q are found in different subtrees, root is LCA
        if (left != nullptr && right != nullptr) {
            return root;
        }

        // If both are in one subtree, return that subtree's result
        return left != nullptr ? left : right;
    }
};

int main() {
    Solution solution;

    // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    //       3
    //      / \
    //     5   1
    //    / \ / \
    //   6  2 0  8
    //     / \
    //    7   4
    TreeNode* root1 = new TreeNode(3);
    root1->left = new TreeNode(5);
    root1->right = new TreeNode(1);
    root1->left->left = new TreeNode(6);
    root1->left->right = new TreeNode(2);
    root1->right->left = new TreeNode(0);
    root1->right->right = new TreeNode(8);
    root1->left->right->left = new TreeNode(7);
    root1->left->right->right = new TreeNode(4);

    TreeNode* p1 = root1->left;  // Node 5
    TreeNode* q1 = root1->right;  // Node 1
    TreeNode* result1 = solution.lowestCommonAncestor(root1, p1, q1);
    cout << "LCA of " << p1->val << " and " << q1->val << ": " << result1->val << endl;  // Expected: 3

    // Example 2: Same tree, p=5, q=4
    TreeNode* p2 = root1->left;  // Node 5
    TreeNode* q2 = root1->left->right->right;  // Node 4
    TreeNode* result2 = solution.lowestCommonAncestor(root1, p2, q2);
    cout << "LCA of " << p2->val << " and " << q2->val << ": " << result2->val << endl;  // Expected: 5

    // Example 3: [1,2]
    //     1
    //      \
    //       2
    TreeNode* root3 = new TreeNode(1);
    root3->right = new TreeNode(2);

    TreeNode* p3 = root3;  // Node 1
    TreeNode* q3 = root3->right;  // Node 2
    TreeNode* result3 = solution.lowestCommonAncestor(root3, p3, q3);
    cout << "LCA of " << p3->val << " and " << q3->val << ": " << result3->val << endl;  // Expected: 1

    return 0;
}

Java

lowest_common_ancestor_of_a_binary_tree_dfs.java

public class Solution {
    /**
     * Find the lowest common ancestor using DFS recursion.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height (call stack depth)
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

        // If either p or q is the current node, it's a potential LCA
        if (root == p || root == q) {
            return root;
        }

        // Search in left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // If both p and q are found in different subtrees, root is LCA
        if (left != null && right != null) {
            return root;
        }

        // If both are in one subtree, return that subtree's result
        return left != null ? left : right;
    }

    // TreeNode definition
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    // Test cases
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
        //       3
        //      / \
        //     5   1
        //    / \ / \
        //   6  2 0  8
        //     / \
        //    7   4
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(5);
        root1.right = new TreeNode(1);
        root1.left.left = new TreeNode(6);
        root1.left.right = new TreeNode(2);
        root1.right.left = new TreeNode(0);
        root1.right.right = new TreeNode(8);
        root1.left.right.left = new TreeNode(7);
        root1.left.right.right = new TreeNode(4);

        TreeNode p1 = root1.left;  // Node 5
        TreeNode q1 = root1.right;  // Node 1
        TreeNode result1 = solution.lowestCommonAncestor(root1, p1, q1);
        System.out.println("LCA of " + p1.val + " and " + q1.val + ": " + result1.val);  // Expected: 3

        // Example 2: Same tree, p=5, q=4
        TreeNode p2 = root1.left;  // Node 5
        TreeNode q2 = root1.left.right.right;  // Node 4
        TreeNode result2 = solution.lowestCommonAncestor(root1, p2, q2);
        System.out.println("LCA of " + p2.val + " and " + q2.val + ": " + result2.val);  // Expected: 5

        // Example 3: [1,2]
        //     1
        //      \
        //       2
        TreeNode root3 = new TreeNode(1);
        root3.right = new TreeNode(2);

        TreeNode p3 = root3;  // Node 1
        TreeNode q3 = root3.right;  // Node 2
        TreeNode result3 = solution.lowestCommonAncestor(root3, p3, q3);
        System.out.println("LCA of " + p3.val + " and " + q3.val + ": " + result3.val);  // Expected: 1
    }
}

JavaScript

lowest_common_ancestor_of_a_binary_tree_dfs.js

/**
 * Definition for a binary tree node.
 */
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * Find the lowest common ancestor using DFS recursion.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height (call stack depth)
 *
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
    if (root === null) {
        return null;
    }

    // If either p or q is the current node, it's a potential LCA
    if (root === p || root === q) {
        return root;
    }

    // Search in left and right subtrees
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);

    // If both p and q are found in different subtrees, root is LCA
    if (left !== null && right !== null) {
        return root;
    }

    // If both are in one subtree, return that subtree's result
    return left !== null ? left : right;
}

// Test cases
if (require.main === module) {
    // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    //       3
    //      / \
    //     5   1
    //    / \ / \
    //   6  2 0  8
    //     / \
    //    7   4
    const root1 = new TreeNode(3);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(1);
    root1.left.left = new TreeNode(6);
    root1.left.right = new TreeNode(2);
    root1.right.left = new TreeNode(0);
    root1.right.right = new TreeNode(8);
    root1.left.right.left = new TreeNode(7);
    root1.left.right.right = new TreeNode(4);

    const p1 = root1.left;  // Node 5
    const q1 = root1.right;  // Node 1
    const result1 = lowestCommonAncestor(root1, p1, q1);
    console.log(`LCA of ${p1.val} and ${q1.val}: ${result1.val}`);  // Expected: 3

    // Example 2: Same tree, p=5, q=4
    const p2 = root1.left;  // Node 5
    const q2 = root1.left.right.right;  // Node 4
    const result2 = lowestCommonAncestor(root1, p2, q2);
    console.log(`LCA of ${p2.val} and ${q2.val}: ${result2.val}`);  // Expected: 5

    // Example 3: [1,2]
    //     1
    //      \
    //       2
    const root3 = new TreeNode(1);
    root3.right = new TreeNode(2);

    const p3 = root3;  // Node 1
    const q3 = root3.right;  // Node 2
    const result3 = lowestCommonAncestor(root3, p3, q3);
    console.log(`LCA of ${p3.val} and ${q3.val}: ${result3.val}`);  // Expected: 1
}

module.exports = lowestCommonAncestor;

Rust

lowest_common_ancestor_of_a_binary_tree_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

impl Solution {
    /**
     * Find the lowest common ancestor using DFS recursion.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height (call stack depth)
     */
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        match root {
            None => None,
            Some(node) => {
                let mut n = node.borrow_mut();

                // If either p or q is the current node, it's a potential LCA
                if let Some(ref p_node) = p {
                    if p_node.borrow().val == n.val {
                        return Some(Rc::clone(&node));
                    }
                }
                if let Some(ref q_node) = q {
                    if q_node.borrow().val == n.val {
                        return Some(Rc::clone(&node));
                    }
                }

                // Search in left and right subtrees
                let left = Solution::lowest_common_ancestor(
                    n.left.take(),
                    p.clone(),
                    q.clone(),
                );
                let right = Solution::lowest_common_ancestor(
                    n.right.take(),
                    p.clone(),
                    q.clone(),
                );

                // If both p and q are found in different subtrees, root is LCA
                match (&left, &right) {
                    (Some(_), Some(_)) => Some(Rc::clone(&node)),
                    (Some(l), None) => Some(Rc::clone(l)),
                    (None, Some(r)) => Some(Rc::clone(r)),
                    (None, None) => None,
                }
            }
        }
    }
}

pub struct Solution;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example_1() {
        // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
        //       3
        //      / \
        //     5   1
        //    / \ / \
        //   6  2 0  8
        //     / \
        //    7   4
        let root = Rc::new(RefCell::new(TreeNode::new(3)));
        let node5 = Rc::new(RefCell::new(TreeNode::new(5)));
        let node1 = Rc::new(RefCell::new(TreeNode::new(1)));

        root.borrow_mut().left = Some(Rc::clone(&node5));
        root.borrow_mut().right = Some(Rc::clone(&node1));

        let result = Solution::lowest_common_ancestor(
            Some(Rc::clone(&root)),
            Some(Rc::clone(&node5)),
            Some(Rc::clone(&node1)),
        );

        assert_eq!(result.map(|r| r.borrow().val), Some(3));
    }
}

Go

lowest_common_ancestor_of_a_binary_tree_dfs.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * Find the lowest common ancestor using DFS recursion.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height (call stack depth)
 */
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil {
    return nil
  }

  // If either p or q is the current node, it's a potential LCA
  if root == p || root == q {
    return root
  }

  // Search in left and right subtrees
  left := LowestCommonAncestor(root.Left, p, q)
  right := LowestCommonAncestor(root.Right, p, q)

  // If both p and q are found in different subtrees, root is LCA
  if left != nil && right != nil {
    return root
  }

  // If both are in one subtree, return that subtree's result
  if left != nil {
    return left
  }
  return right
}

func main() {
  // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
  //       3
  //      / \
  //     5   1
  //    / \ / \
  //   6  2 0  8
  //     / \
  //    7   4
  root1 := &TreeNode{Val: 3}
  root1.Left = &TreeNode{Val: 5}
  root1.Right = &TreeNode{Val: 1}
  root1.Left.Left = &TreeNode{Val: 6}
  root1.Left.Right = &TreeNode{Val: 2}
  root1.Right.Left = &TreeNode{Val: 0}
  root1.Right.Right = &TreeNode{Val: 8}
  root1.Left.Right.Left = &TreeNode{Val: 7}
  root1.Left.Right.Right = &TreeNode{Val: 4}

  p1 := root1.Left  // Node 5
  q1 := root1.Right // Node 1
  result1 := LowestCommonAncestor(root1, p1, q1)
  fmt.Printf("LCA of %d and %d: %d\n", p1.Val, q1.Val, result1.Val) // Expected: 3

  // Example 2: Same tree, p=5, q=4
  p2 := root1.Left              // Node 5
  q2 := root1.Left.Right.Right  // Node 4
  result2 := LowestCommonAncestor(root1, p2, q2)
  fmt.Printf("LCA of %d and %d: %d\n", p2.Val, q2.Val, result2.Val) // Expected: 5

  // Example 3: [1,2]
  //     1
  //      \
  //       2
  root3 := &TreeNode{Val: 1}
  root3.Right = &TreeNode{Val: 2}

  p3 := root3       // Node 1
  q3 := root3.Right // Node 2
  result3 := LowestCommonAncestor(root3, p3, q3)
  fmt.Printf("LCA of %d and %d: %d\n", p3.Val, q3.Val, result3.Val) // Expected: 1
}

Approach 2: Parent Pointers + Hash Set

🎯 Interview Favourite

Store parent pointers for each node during a DFS traversal. Then, for node p, collect all ancestors in a hash set. Walk up from q using parent pointers until finding a node in the set.

This approach separates the traversal (finding nodes and storing parents) from the LCA search.

⏱ Time O(n) One DFS to find parents, then walk ancestors 💾 Space O(h) Hash set of ancestors

Step-by-step Example

Input: Tree with nodes [3,5,1,6,2,0,8], p = 5, q = 1

Step 1: Find p and store all ancestors of p:

DFS traversal finds p=5
Ancestors of 5: {5, 3}  // 5 itself and its ancestor 3

Step 2: Walk from q upward, check each ancestor against the set:

Walk from q=1:
  Check 1 → not in {5, 3}
  Check parent(1)=3 → found in set!
  LCA is 3 ✓

Pseudocode

function lca(root, p, q):
    parent = {}
    visited = set()

    // DFS to store parent pointers
    function dfs(node):
        if node is null:
            return
        visited.add(node)
        if node.left is not null:
            parent[node.left] = node
            dfs(node.left)
        if node.right is not null:
            parent[node.right] = node
            dfs(node.right)

    dfs(root)

    // Collect all ancestors of p
    ancestors = set()
    current = p
    while current is not null:
        ancestors.add(current)
        current = parent.get(current)

    // Walk from q up to find first ancestor in set
    current = q
    while current not in ancestors:
        current = parent.get(current)

    return current

Solution Code

Python

lowest_common_ancestor_of_a_binary_tree_parent_pointers.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowestCommonAncestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> TreeNode:
    """
    Find the lowest common ancestor using parent pointers and hash set.

    Time Complexity: O(n) where n is the number of nodes
    Space Complexity: O(h) where h is the height
    """
    parent = {}
    visited = set()

    def dfs(node):
        """Store parent pointers for all nodes."""
        if node is None:
            return
        visited.add(node)
        if node.left:
            parent[node.left] = node
            dfs(node.left)
        if node.right:
            parent[node.right] = node
            dfs(node.right)

    # Build parent pointers
    dfs(root)

    # Collect all ancestors of p
    ancestors = set()
    current = p
    while current:
        ancestors.add(current)
        current = parent.get(current)

    # Walk from q up to find first common ancestor
    current = q
    while current not in ancestors:
        current = parent.get(current)

    return current


# Test cases
if __name__ == "__main__":
    # Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    #       3
    #      / \
    #     5   1
    #    / \ / \
    #   6  2 0  8
    #     / \
    #    7   4
    root1 = TreeNode(3)
    root1.left = TreeNode(5)
    root1.right = TreeNode(1)
    root1.left.left = TreeNode(6)
    root1.left.right = TreeNode(2)
    root1.right.left = TreeNode(0)
    root1.right.right = TreeNode(8)
    root1.left.right.left = TreeNode(7)
    root1.left.right.right = TreeNode(4)

    p1 = root1.left  # Node 5
    q1 = root1.right  # Node 1
    result1 = lowestCommonAncestor(root1, p1, q1)
    print(f"LCA of {p1.val} and {q1.val}: {result1.val}")  # Expected: 3

    # Example 2: Same tree, p=5, q=4
    p2 = root1.left  # Node 5
    q2 = root1.left.right.right  # Node 4
    result2 = lowestCommonAncestor(root1, p2, q2)
    print(f"LCA of {p2.val} and {q2.val}: {result2.val}")  # Expected: 5

    # Example 3: [1,2]
    #     1
    #      \
    #       2
    root3 = TreeNode(1)
    root3.right = TreeNode(2)

    p3 = root3  # Node 1
    q3 = root3.right  # Node 2
    result3 = lowestCommonAncestor(root3, p3, q3)
    print(f"LCA of {p3.val} and {q3.val}: {result3.val}")  # Expected: 1

C++

lowest_common_ancestor_of_a_binary_tree_parent_pointers.cpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

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

class Solution {
private:
    unordered_map<TreeNode*, TreeNode*> parent;

    void dfs(TreeNode* node) {
        if (node == nullptr) {
            return;
        }
        if (node->left) {
            parent[node->left] = node;
            dfs(node->left);
        }
        if (node->right) {
            parent[node->right] = node;
            dfs(node->right);
        }
    }

public:
    /**
     * Find the lowest common ancestor using parent pointers and hash set.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height
     */
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        parent.clear();
        dfs(root);

        // Collect all ancestors of p
        unordered_set<TreeNode*> ancestors;
        TreeNode* current = p;
        while (current) {
            ancestors.insert(current);
            if (parent.find(current) == parent.end()) {
                break;
            }
            current = parent[current];
        }

        // Walk from q up to find first common ancestor
        current = q;
        while (ancestors.find(current) == ancestors.end()) {
            if (parent.find(current) == parent.end()) {
                break;
            }
            current = parent[current];
        }

        return current;
    }
};

int main() {
    Solution solution;

    // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    //       3
    //      / \
    //     5   1
    //    / \ / \
    //   6  2 0  8
    //     / \
    //    7   4
    TreeNode* root1 = new TreeNode(3);
    root1->left = new TreeNode(5);
    root1->right = new TreeNode(1);
    root1->left->left = new TreeNode(6);
    root1->left->right = new TreeNode(2);
    root1->right->left = new TreeNode(0);
    root1->right->right = new TreeNode(8);
    root1->left->right->left = new TreeNode(7);
    root1->left->right->right = new TreeNode(4);

    TreeNode* p1 = root1->left;  // Node 5
    TreeNode* q1 = root1->right;  // Node 1
    TreeNode* result1 = solution.lowestCommonAncestor(root1, p1, q1);
    cout << "LCA of " << p1->val << " and " << q1->val << ": " << result1->val << endl;  // Expected: 3

    // Example 2: Same tree, p=5, q=4
    TreeNode* p2 = root1->left;  // Node 5
    TreeNode* q2 = root1->left->right->right;  // Node 4
    TreeNode* result2 = solution.lowestCommonAncestor(root1, p2, q2);
    cout << "LCA of " << p2->val << " and " << q2->val << ": " << result2->val << endl;  // Expected: 5

    // Example 3: [1,2]
    //     1
    //      \
    //       2
    TreeNode* root3 = new TreeNode(1);
    root3->right = new TreeNode(2);

    TreeNode* p3 = root3;  // Node 1
    TreeNode* q3 = root3->right;  // Node 2
    TreeNode* result3 = solution.lowestCommonAncestor(root3, p3, q3);
    cout << "LCA of " << p3->val << " and " << q3->val << ": " << result3->val << endl;  // Expected: 1

    return 0;
}

Java

lowest_common_ancestor_of_a_binary_tree_parent_pointers.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    private Map<TreeNode, TreeNode> parent = new HashMap<>();

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            parent.put(node.left, node);
            dfs(node.left);
        }
        if (node.right != null) {
            parent.put(node.right, node);
            dfs(node.right);
        }
    }

    /**
     * Find the lowest common ancestor using parent pointers and hash set.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        parent.clear();
        dfs(root);

        // Collect all ancestors of p
        Set<TreeNode> ancestors = new HashSet<>();
        TreeNode current = p;
        while (current != null) {
            ancestors.add(current);
            current = parent.get(current);
        }

        // Walk from q up to find first common ancestor
        current = q;
        while (!ancestors.contains(current)) {
            current = parent.get(current);
        }

        return current;
    }

    // TreeNode definition
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    // Test cases
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
        //       3
        //      / \
        //     5   1
        //    / \ / \
        //   6  2 0  8
        //     / \
        //    7   4
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(5);
        root1.right = new TreeNode(1);
        root1.left.left = new TreeNode(6);
        root1.left.right = new TreeNode(2);
        root1.right.left = new TreeNode(0);
        root1.right.right = new TreeNode(8);
        root1.left.right.left = new TreeNode(7);
        root1.left.right.right = new TreeNode(4);

        TreeNode p1 = root1.left;  // Node 5
        TreeNode q1 = root1.right;  // Node 1
        TreeNode result1 = solution.lowestCommonAncestor(root1, p1, q1);
        System.out.println("LCA of " + p1.val + " and " + q1.val + ": " + result1.val);  // Expected: 3

        // Example 2: Same tree, p=5, q=4
        TreeNode p2 = root1.left;  // Node 5
        TreeNode q2 = root1.left.right.right;  // Node 4
        TreeNode result2 = solution.lowestCommonAncestor(root1, p2, q2);
        System.out.println("LCA of " + p2.val + " and " + q2.val + ": " + result2.val);  // Expected: 5

        // Example 3: [1,2]
        //     1
        //      \
        //       2
        TreeNode root3 = new TreeNode(1);
        root3.right = new TreeNode(2);

        TreeNode p3 = root3;  // Node 1
        TreeNode q3 = root3.right;  // Node 2
        TreeNode result3 = solution.lowestCommonAncestor(root3, p3, q3);
        System.out.println("LCA of " + p3.val + " and " + q3.val + ": " + result3.val);  // Expected: 1
    }
}

JavaScript

lowest_common_ancestor_of_a_binary_tree_parent_pointers.js

/**
 * Definition for a binary tree node.
 */
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * Find the lowest common ancestor using parent pointers and hash set.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height
 *
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
    const parent = new Map();

    function dfs(node) {
        if (node === null) {
            return;
        }
        if (node.left) {
            parent.set(node.left, node);
            dfs(node.left);
        }
        if (node.right) {
            parent.set(node.right, node);
            dfs(node.right);
        }
    }

    // Build parent pointers
    dfs(root);

    // Collect all ancestors of p
    const ancestors = new Set();
    let current = p;
    while (current) {
        ancestors.add(current);
        current = parent.get(current);
    }

    // Walk from q up to find first common ancestor
    current = q;
    while (!ancestors.has(current)) {
        current = parent.get(current);
    }

    return current;
}

// Test cases
if (require.main === module) {
    // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
    //       3
    //      / \
    //     5   1
    //    / \ / \
    //   6  2 0  8
    //     / \
    //    7   4
    const root1 = new TreeNode(3);
    root1.left = new TreeNode(5);
    root1.right = new TreeNode(1);
    root1.left.left = new TreeNode(6);
    root1.left.right = new TreeNode(2);
    root1.right.left = new TreeNode(0);
    root1.right.right = new TreeNode(8);
    root1.left.right.left = new TreeNode(7);
    root1.left.right.right = new TreeNode(4);

    const p1 = root1.left;  // Node 5
    const q1 = root1.right;  // Node 1
    const result1 = lowestCommonAncestor(root1, p1, q1);
    console.log(`LCA of ${p1.val} and ${q1.val}: ${result1.val}`);  // Expected: 3

    // Example 2: Same tree, p=5, q=4
    const p2 = root1.left;  // Node 5
    const q2 = root1.left.right.right;  // Node 4
    const result2 = lowestCommonAncestor(root1, p2, q2);
    console.log(`LCA of ${p2.val} and ${q2.val}: ${result2.val}`);  // Expected: 5

    // Example 3: [1,2]
    //     1
    //      \
    //       2
    const root3 = new TreeNode(1);
    root3.right = new TreeNode(2);

    const p3 = root3;  // Node 1
    const q3 = root3.right;  // Node 2
    const result3 = lowestCommonAncestor(root3, p3, q3);
    console.log(`LCA of ${p3.val} and ${q3.val}: ${result3.val}`);  // Expected: 1
}

module.exports = lowestCommonAncestor;

Rust

lowest_common_ancestor_of_a_binary_tree_parent_pointers.rs

use std::cell::RefCell;
use std::collections::{HashMap, HashSet};
use std::rc::Rc;

#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

impl Solution {
    /**
     * Find the lowest common ancestor using parent pointers and hash set.
     *
     * Time Complexity: O(n) where n is the number of nodes
     * Space Complexity: O(h) where h is the height
     */
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let mut parent: HashMap<i32, Option<i32>> = HashMap::new();

        fn dfs(
            node: &Option<Rc<RefCell<TreeNode>>>,
            parent: &mut HashMap<i32, Option<i32>>,
        ) {
            if let Some(n) = node {
                let n_ref = n.borrow();
                parent.insert(n_ref.val, None); // Initialize without parent

                if let Some(left) = &n_ref.left {
                    parent.insert(left.borrow().val, Some(n_ref.val));
                    dfs(&Some(Rc::clone(left)), parent);
                }
                if let Some(right) = &n_ref.right {
                    parent.insert(right.borrow().val, Some(n_ref.val));
                    dfs(&Some(Rc::clone(right)), parent);
                }
            }
        }

        dfs(&root, &mut parent);

        // Collect ancestors of p
        let mut ancestors = HashSet::new();
        if let Some(p_node) = &p {
            let mut current = Some(p_node.borrow().val);
            while let Some(val) = current {
                ancestors.insert(val);
                current = parent.get(&val).and_then(|&p| p);
            }
        }

        // Walk from q upward to find first common ancestor
        if let Some(q_node) = q {
            let mut current = Some(q_node.borrow().val);
            while let Some(val) = current {
                if ancestors.contains(&val) {
                    // Find the node with this value in the tree
                    fn find_node(node: &Option<Rc<RefCell<TreeNode>>>, val: i32) -> Option<Rc<RefCell<TreeNode>>> {
                        if let Some(n) = node {
                            let n_ref = n.borrow();
                            if n_ref.val == val {
                                return Some(Rc::clone(n));
                            }
                            if let Some(found) = find_node(&n_ref.left, val) {
                                return Some(found);
                            }
                            find_node(&n_ref.right, val)
                        } else {
                            None
                        }
                    }

                    return find_node(&root, val);
                }
                current = parent.get(&val).and_then(|&p| p);
            }
        }

        None
    }
}

pub struct Solution;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_example_1() {
        // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
        //       3
        //      / \
        //     5   1
        //    / \ / \
        //   6  2 0  8
        //     / \
        //    7   4
        let root = Rc::new(RefCell::new(TreeNode::new(3)));
        let node5 = Rc::new(RefCell::new(TreeNode::new(5)));
        let node1 = Rc::new(RefCell::new(TreeNode::new(1)));

        root.borrow_mut().left = Some(Rc::clone(&node5));
        root.borrow_mut().right = Some(Rc::clone(&node1));

        let result = Solution::lowest_common_ancestor(
            Some(Rc::clone(&root)),
            Some(Rc::clone(&node5)),
            Some(Rc::clone(&node1)),
        );

        assert_eq!(result.map(|r| r.borrow().val), Some(3));
    }
}

Go

lowest_common_ancestor_of_a_binary_tree_parent_pointers.go

package main

import "fmt"

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

/**
 * Find the lowest common ancestor using parent pointers and hash set.
 *
 * Time Complexity: O(n) where n is the number of nodes
 * Space Complexity: O(h) where h is the height
 */
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  parent := make(map[*TreeNode]*TreeNode)

  var dfs func(*TreeNode)
  dfs = func(node *TreeNode) {
    if node == nil {
      return
    }
    if node.Left != nil {
      parent[node.Left] = node
      dfs(node.Left)
    }
    if node.Right != nil {
      parent[node.Right] = node
      dfs(node.Right)
    }
  }

  // Build parent pointers
  dfs(root)

  // Collect all ancestors of p
  ancestors := make(map[*TreeNode]bool)
  current := p
  for current != nil {
    ancestors[current] = true
    current = parent[current]
  }

  // Walk from q up to find first common ancestor
  current = q
  for !ancestors[current] {
    current = parent[current]
  }

  return current
}

func main() {
  // Example 1: [3,5,1,6,2,0,8,null,null,7,4]
  //       3
  //      / \
  //     5   1
  //    / \ / \
  //   6  2 0  8
  //     / \
  //    7   4
  root1 := &TreeNode{Val: 3}
  root1.Left = &TreeNode{Val: 5}
  root1.Right = &TreeNode{Val: 1}
  root1.Left.Left = &TreeNode{Val: 6}
  root1.Left.Right = &TreeNode{Val: 2}
  root1.Right.Left = &TreeNode{Val: 0}
  root1.Right.Right = &TreeNode{Val: 8}
  root1.Left.Right.Left = &TreeNode{Val: 7}
  root1.Left.Right.Right = &TreeNode{Val: 4}

  p1 := root1.Left  // Node 5
  q1 := root1.Right // Node 1
  result1 := LowestCommonAncestor(root1, p1, q1)
  fmt.Printf("LCA of %d and %d: %d\n", p1.Val, q1.Val, result1.Val) // Expected: 3

  // Example 2: Same tree, p=5, q=4
  p2 := root1.Left              // Node 5
  q2 := root1.Left.Right.Right  // Node 4
  result2 := LowestCommonAncestor(root1, p2, q2)
  fmt.Printf("LCA of %d and %d: %d\n", p2.Val, q2.Val, result2.Val) // Expected: 5

  // Example 3: [1,2]
  //     1
  //      \
  //       2
  root3 := &TreeNode{Val: 1}
  root3.Right = &TreeNode{Val: 2}

  p3 := root3       // Node 1
  q3 := root3.Right // Node 2
  result3 := LowestCommonAncestor(root3, p3, q3)
  fmt.Printf("LCA of %d and %d: %d\n", p3.Val, q3.Val, result3.Val) // Expected: 1
}

Related Problems

• Lowest Common Ancestor of a Binary Search Tree ↗ Medium #235
• Lowest Common Ancestor of a Binary Tree II ↗ Medium #1644
• Lowest Common Ancestor of a Binary Tree III ↗ Medium #1650
• Lowest Common Ancestor of a Binary Tree IV ↗ Medium #1676

Interview Tips

Key trade-offs to discuss

• DFS vs Parent Pointers: DFS is simpler and more elegant; parent pointers are more flexible if you need multiple LCA queries.
• Single pass vs multiple passes: DFS does it in one recursive pass; parent pointers require explicit parent storage.
• Memory usage: Both are O(h), but parent pointers use explicit dictionary space.
• Follow-ups to expect: handling BST version, handling null inputs, multiple nodes, or finding all LCAs.

← Previous
#235 Lowest Common Ancestor of a Binary Search Tree Next
#237 Delete Node in a Linked List →