How to Find the Lowest Common Ancestor (LCA) in a Binary Tree

Use a recursive post-order DFS that returns a node when it finds either target, and when both left and right subtrees return non-null values, the current node is the LCA.

Finding the lowest common ancestor (LCA) in a binary tree is a fundamental algorithmic problem frequently encountered in technical interviews and tree-based data processing. This guide examines the optimal recursive solution implemented in the kdn251/interviews repository, providing a complete breakdown of how to find the LCA in a binary tree with O(N) time complexity.

What Is the Lowest Common Ancestor in a Binary Tree?

The lowest common ancestor (LCA) of two nodes p and q in a binary tree is defined as the deepest node that has both p and q as descendants, where a node is considered a descendant of itself. In practical terms, the LCA represents the shared parent node located farthest from the root where the paths to both target nodes diverge.

Recursive DFS Approach to Find LCA in a Binary Tree

The most efficient method to locate the LCA employs a post-order depth-first search (DFS) that traverses from the leaves upward, propagating node references only when targets are discovered.

Algorithm Logic

The recursive strategy follows three distinct phases:

1. Base case handling – If the current root is null, or if root matches either p or q, immediately return root. This captures the scenario where one target is the ancestor of the other.

2. Subtree exploration – Recursively invoke the LCA search on root.left and root.right to probe both subtrees for the target nodes.

3. Result combination –

   • If both left and right recursive calls return non-null values, the current root represents the split point where p and q reside in different subtrees, making root the LCA.
   • If only one side returns a non-null node, propagate that result upward, as it contains either one of the targets or the LCA discovered deeper in that branch.

Complexity Analysis

• Time Complexity: O(N) where N is the number of nodes in the tree. The algorithm visits each node exactly once in the worst case.
• Space Complexity: O(H) where H is the height of the tree, representing the maximum recursion stack depth. In a skewed tree, this degrades to O(N), while a balanced tree requires O(log N).

Java Implementation from kdn251/interviews

The kdn251/interviews repository provides a clean, production-ready implementation in leetcode/tree/LowestCommonAncestorOfABinaryTree.java. The lowestCommonAncestor method implements the exact recursive post-order strategy described above:

public class LowestCommonAncestorOfABinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;                     // base case
        }

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

        if (left != null && right != null) { // p on one side, q on the other
            return root;                     // current node is LCA
        }

        return left == null ? right : left;  // propagate non-null result
    }
}

This implementation handles all edge cases, including scenarios where one node is the direct ancestor of the other, by returning immediately when a match is found and allowing that result to propagate upward.

Practical Examples

Basic Usage

Consider a binary tree structured as follows:

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

To find the LCA of nodes 5 and 1:

// Construct the tree
TreeNode root = new TreeNode(3);
root.left = new TreeNode(5);
root.right = new TreeNode(1);
// ... (additional node construction)

LowestCommonAncestorOfABinaryTree solver = new LowestCommonAncestorOfABinaryTree();
TreeNode lca = solver.lowestCommonAncestor(root, root.left, root.right);
System.out.println(lca.val); // Output: 3

To find the LCA of nodes 5 and 4 (where 5 is the ancestor of 4):

TreeNode node4 = root.left.right.right; // Node with value 4
TreeNode lca2 = solver.lowestCommonAncestor(root, root.left, node4);
System.out.println(lca2.val); // Output: 5

Edge Cases

The algorithm gracefully handles several boundary conditions:

• One node is the ancestor of the other – The base case if (root == null || root == p || root == q) immediately returns the current node when it matches either target. If one target is the ancestor of the other, the ancestor will be encountered first and returned, then propagated upward as the LCA without further searching the descendant's subtree.
• One or both nodes missing – If either p or q does not exist in the tree, the algorithm returns the existing node (or null if neither exists), as only the found node propagates upward.
• Identical nodes – When p and q refer to the same node, the base case triggers on the first encounter and returns that node immediately.

Repository Structure and Related Files

The kdn251/interviews repository organizes this solution across multiple interview preparation tracks. The core implementation resides in the LeetCode section, with identical copies adapted for specific company interview sets:

Path	Description
leetcode/tree/LowestCommonAncestorOfABinaryTree.java	Core recursive solution for LeetCode problem 236.
company/amazon/LowestCommonAncestorOfABinaryTree.java	Amazon interview preparation variant.
company/facebook/LowestCommonAncestorOfABinaryTree.java	Facebook interview preparation variant.
company/linkedin/LowestCommonAncestorOfABinaryTree.java	LinkedIn interview preparation variant.
company/twitter/LowestCommonAncestorOfABinaryTree.java	Twitter interview preparation variant.

All implementations share the identical O(N) time and O(H) space recursive strategy, ensuring consistent performance across different interview contexts.

Summary

• The lowest common ancestor (LCA) in a binary tree is the deepest node where paths to two target nodes diverge.
• The optimal solution uses post-order DFS recursion with O(N) time complexity and O(H) space complexity.
• The algorithm returns immediately when encountering null, p, or q, then propagates the first non-null result upward until both left and right subtrees return values, identifying the LCA.
• The kdn251/interviews repository provides this implementation in leetcode/tree/LowestCommonAncestorOfABinaryTree.java and across multiple company-specific interview directories.

Frequently Asked Questions

What is the time complexity of finding the LCA in a binary tree?

The recursive DFS approach runs in O(N) time where N is the number of nodes, because in the worst case it must visit every node in the tree once to locate both target nodes.

Can the LCA algorithm handle cases where one node is the ancestor of the other?

Yes. The base case if (root == null || root == p || root == q) immediately returns the current node when it matches either target. If one target is the ancestor of the other, the ancestor will be encountered first and returned, then propagated upward as the LCA without further searching the descendant's subtree.

What is the space complexity of the recursive LCA solution?

The space complexity is O(H) where H is the height of the tree, representing the maximum recursion stack depth. In a balanced binary tree this is O(log N), but it degrades to O(N) in a skewed tree where each node has only one child.

Where can I find the complete implementation in the kdn251/interviews repository?

The primary implementation resides in leetcode/tree/LowestCommonAncestorOfABinaryTree.java. Identical copies adapted for specific company interview tracks are also available in company/amazon/, company/facebook/, company/linkedin/, company/twitter/, and other directories within the repository.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}