LeetCode 236. Lowest Common Ancestor of a Binary Tree

Posted on In , Views:

🧩 Problem Description

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

The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

💬 Example

Example 1

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.

💡 Approach: Recursive DFS

We traverse the binary tree recursively:

  • If the current node is null, return null.
  • If the current node matches p or q, return it.
  • Recursively search left and right subtrees.
  • If both left and right return non-null, the current node is the LCA.
  • Otherwise, return the non-null child.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {{
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {{
        if (root == null || root == p || root == q) {{
            return root;
        }}

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) {{
            return root;
        }}

        return left != null ? left : right;
    }}
}}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visiting each node once
  • Space Complexity: O(h) — recursion stack, where h is the tree height

✍️ Summary

  • This is a classic DFS + recursion problem on binary trees.
  • We find the split point where p and q diverge in different subtrees.
  • Related problems:
    • lc-235 — LCA of a BST (simpler due to BST property)
    • lc-236 — LCA of any binary tree (this one)