236. Lowest Common Ancestor of a Binary Tree

At a Glance

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

Problem (one-liner)

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).

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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