What is the brute force approach and complexity for Lowest Common Ancestor of a Binary Tree?

For each node, check whether its subtree holds both p and q; keep the deepest one that does with time complexity O(N²) and space complexity O(H).

What is the optimal approach and complexity for Lowest Common Ancestor of a Binary Tree?

Each node asks its children what they found; if both sides found something, this node is the answer with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Lowest Common Ancestor of a Binary Tree?

Look for key signals in the prompt: "binary tree (no sorted order)" indicates Values say nothing about the side. Every subtree has to be checked, so each child must report back to its parent. This is a Tree DFS with a bottom-up answer.; "two nodes p and q" indicates Each call returns p or q when it finds one, so the split is found by combining what the two sides report.; "a node can be its own ancestor" indicates If a node is p or q, it returns itself at once. That covers the case where one target is above the other..

Lowest Common Ancestor of a Binary Tree

Medium·LeetCode #236 Pro OnlyMedium

LeetCode

Problem Statement

You are given the root of a binary tree and two nodes p and q that are both in the tree. The tree is not sorted, so a node's value tells you nothing about where it is.

Find the lowest common ancestor (LCA) of p and q. This is the lowest node that has both p and q below it. A node counts as its own ancestor.

Return the node itself, not its value.

Input

root, the root of a binary tree, and two different node pointers p and q.

Output

The node that is the lowest common ancestor of p and q.

Example 1

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 1

Output: 3

5 is in the left subtree of 3 and 1 is in the right subtree, so 3 is the first node that splits them.

Example 2

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4

Output: 5

4 is below 5. A node counts as its own ancestor, so the answer is 5 itself.

Example 3

Input: root = [1, 2], p = 1, q = 2

Output: 1

2 is the child of 1, so the answer is 1.

Constraints

• The number of nodes in the tree is in the range [2, 10^5].
• −10^9 ≤ Node.val ≤ 10^9
• All Node.val are unique.
• p ≠ q
• p and q will exist in the tree.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“binary tree (no sorted order)”

→ Values say nothing about the side. Every subtree has to be checked, so each child must report back to its parent. This is a Tree DFS with a bottom-up answer.

“two nodes p and q”

→ Each call returns p or q when it finds one, so the split is found by combining what the two sides report.

“a node can be its own ancestor”

→ If a node is p or q, it returns itself at once. That covers the case where one target is above the other.

Approach Complexity Ladder

Brute Force — check every node's subtreeO(N²)O(H)

For each node, check whether its subtree holds both p and q; keep the deepest one that does

Better — find both root paths, then compare themO(N)O(N)

Two DFS calls record the root-to-p and root-to-q paths; the last node both paths share is the answer

Optimal — one post-order passO(N)O(H)

Each node asks its children what they found; if both sides found something, this node is the answer

Brute Force Intuition

A node is a common ancestor when its subtree contains both p and q. So check every node: search its subtree for p and for q. Among all the nodes that pass, the deepest one is the lowest common ancestor.

Recognition rule for this sub-pattern:

The LCA is the first node where the two targets split into different subtrees.

Remember this · Tree DFS

Trigger

Paths, heights, diameters, validating structure, ancestors, anything "for every subtree".

Think

If my left and right children already gave me their answers, how do I build mine?

Key question

What does my recursive function return, and what do I pass down?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture