236. Lowest Common Ancestor of a Binary Tree

Quick Identifier

• Topic: trees
• Pattern: Tree DFS
• Difficulty: Medium
• Companies: Amazon, Facebook, Google, Microsoft, Apple
• Frequency: Very High
• LeetCode: 236

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree and two distinct nodes primary and secondary that exist in the tree, return their lowest common ancestor—the deepest node that has both given nodes as descendants (a node may be a descendant of itself).

Concept Explanation

Given the root of a binary tree and two distinct nodes primary and secondary that exist in the tree, return their lowest common ancestor—the deepest node that has both given nodes as descendants (a node may be a descendant of itself).

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• LCA in a general binary tree (not BST) without parent pointers
• Single recursive function returns: match if subtree contains target(s); answer bubbles when left and right searches both find targets
• Often three-valued logic: return left result, right result, or split at current

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — store paths to both nodes, compare prefixes — O(n) time / O(n) space — acceptable but two passes.
• Optimal — one post-order DFS — O(n) time / O(h) stack — if current equals either target, return it; else delegate to children; if both sides non-null, current is LCA.

Optimal Solution

Go

package main

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

func lowestCommonAncestor(root *TreeNode, primary *TreeNode, secondary *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root == primary || root == secondary {
		return root
	}
	leftResult := lowestCommonAncestor(root.Left, primary, secondary)
	rightResult := lowestCommonAncestor(root.Right, primary, secondary)
	if leftResult != nil && rightResult != nil {
		return root
	}
	if leftResult != nil {
		return leftResult
	}
	return rightResult
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function lowestCommonAncestor(root, primary, secondary) {
	if (root === null) {
		return null;
	}
	if (root === primary || root === secondary) {
		return root;
	}
	const leftResult = lowestCommonAncestor(root.left, primary, secondary);
	const rightResult = lowestCommonAncestor(root.right, primary, secondary);
	if (leftResult !== null && rightResult !== null) {
		return root;
	}
	return leftResult !== null ? leftResult : rightResult;
}

Walkthrough

Primary 5, secondary 1 in a tree where 3 is root, 5 and 1 in different subtrees under 3.

If one target is ancestor of the other, first hit on the recursion path short-circuits and returns that ancestor.

Invariant: each call returns the LCA of {primary,secondary} restricted to that subtree, or whichever target lies in that subtree, or null if neither appears below.

Edge Cases

• One node is ancestor of the other — returned immediately when hit
• Balanced vs skew only affects stack depth

Pitfalls

• Reusing the BST-only walking rule from 235 here—wrong without ordering
• Not propagating a found ancestor upward correctly when only one side finds a target

Similar Problems

• 235. Lowest Common Ancestor of a BST — faster split using BST ordering.
• 572. Subtree of Another Tree — another “relationship between two trees” drill.
• 100. Same Tree — building intuition for what subtrees “contain.”

Variants

• Nodes have parent pointers — walk + measure depth / lift deeper pointer.
• LCA of multiple nodes — generalize return logic or iterative Tarjan offline (overkill for interviews).

Mind-Map Tags

#trees #lca #post-order #divide #bubble-result