advanced13 min read·Updated September 30, 2026

LCA in a Binary Tree Explained: Tracing 5 and 4 in [3,5,1,6,2,0,8]

Master LCA in a binary tree (not BST) with a worked example tracing 5, 1, and 4 in [3,5,1,6,2,0,8]. Learn the bottom-up DFS mental model and edge cases.

By Learnisim AI·Published September 30, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Binary tree structure and traversal
  • Depth-First Search (DFS) and recursion
  • Postorder traversal logic
Lowest Common Ancestor (LCA) in a General Binary Tree Bottom-up recursive search without BST ordering invariants Tree Structure: [3, 5, 1, 6, 2, 0, 8, 7, 4] 3 5 1 6 2 0 8 7 4 Query 1: LCA(5, 1) = Root 3 • 5 is in left subtree, 1 is in right subtree. • Root 3 detects split and returns itself immediately. Query 2: LCA(5, 4) = Node 5 • Node 5 matches first; returns upward before checking 4. Bottom-Up Postorder Recursive Logic 1. Base Case / Target Match If root is None or matches p or q, return root. 2. Recursive Descent left = LCA(root.left), right = LCA(root.right) 3. Intersection & Bubble-Up Decision • If BOTH left and right are non-null → Current is LCA. • If only one is non-null → Bubble up that child result. • If neither → Return None. Python Snippet: if not root or root == p or root == q: return root left, right = lca(root.left, p, q), lca(root.right, p, q) return root if (left and right) else (left or right)
LCA of 5 and 1, then of 5 and 4, in [3,5,1,6,2,0,8] with 2 having 7,4 overview diagram
Why

Why Standard Tree Searches Fail for Lowest Common Ancestor

Phase 1: The Problem with Unordered Trees

Imagine you are handed a binary tree rooted at 3, where the left child is 5 and the right child is 1. The node 5 has children 6 and 2, and node 2 branches further into 7 and 4. Meanwhile, node 1 has children 0 and 8. You are asked to find the Lowest Common Ancestor in a binary tree (not BST) explained through two specific queries: first, find the LCA of node 5 and node 1; second, find the LCA of node 5 and node 4.
In a Binary Search Tree (BST), this task is trivial. If both target nodes are smaller than the current node, you simply step left; if both are larger, you step right. The first time your traversal splits or equals one of the targets, you have your LCA. But our tree breaks this shortcut entirely. Node 1 sits on the right of root 3, yet its descendants 0 and 8 interleave with values found under the left subtree. Without the strict left-less-than-right invariant, a naive descent will wander down the wrong branch and miss the shared ancestor completely.
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
When we look for LCA(5, 1), root 3 immediately separates them—5 is in the left subtree and 1 is in the right subtree. But when we look for LCA(5, 4), both nodes live inside the exact same left branch. Node 5 is an ancestor of node 2, which in turn is an ancestor of node 4. A simple top-down check cannot easily determine whether 4 actually exists deep below 5 or if we are heading down a dead end without backtracking or exploring both paths.
Why Standard Tree Searches Fail for Lowest Common Ancestor (LCA) Binary Tree [3, 5, 1, 6, 2, 0, 8, 7, 4] 3 5 1 6 2 0 8 7 4 • Node 5: Target 1 (and ancestor) • Node 1: Target 2 (cross-tree branch) • Node 4: Target 3 (deep descendant of 5) Two Queries & BST Failure Reality Query A: LCA( 5, 1 ) • Root 3 immediately splits them (5 left, 1 right). • Split point found instantly! LCA = 3. Easy (BST-like) Query B: LCA( 5, 4 ) • Both nodes live entirely in the LEFT subtree! • Node 5 is an ancestor of 4 (via node 2). • BST logic breaks: values do not sort left/right. Hard / Tricky Why standard descent fails: Without sorted invariants, you cannot know if node 4 lies below 5 without exploring both subtrees fully.
Why Standard Tree Searches Fail for Lowest Common Ancestor diagram
Model

Defining LCA in a General Binary Tree via Subtree Intersections

Phase 2: The Core Mental Model

To find the LCA of two nodes like 5 and 1 in our tree rooted at 3, we must abandon any notion of comparing values as we would in a Binary Search Tree. Since node values are arbitrary, our only compass is structural: we must search downward and inspect what each subtree contains.
Imagine standing at the root node 3. You send two scouts downward: one to the left subtree rooted at 5, and one to the right subtree rooted at 1. If target 5 is found somewhere down the left path and target 1 is found down the right path, node 3 instantly recognizes it is the meeting point where the paths diverge. Therefore, node 3 is the LCA for targets 5 and 1.
Now consider finding the LCA of 5 and 4, where 4 is a child of 2, which is a child of 5. When our scout enters the subtree rooted at 5, it immediately encounters node 5 itself. If we define our recursive search to report back the moment it hits either target node, the scout at 5 reports success upward before even exploring deeper into 2 or its children . Because target 4 lives entirely inside the subtree of 5, the right branch from the root returns null, and node 5 itself becomes the Lowest Common Ancestor.

The Recursive Anatomy

At any arbitrary node during our traversal, exactly three structural questions matter:
1. Is this current node equal to or ?
2.What do my left and right recursive children report back?
3.Do both my left and right branches return a non-null node?
If the answer to the third question is yes, the current node is the exact pivot point—the lowest common ancestor where the search paths from and intersect for the first time.
Lowest Common Ancestor (LCA) in a Binary Tree Subtree Intersections & Recursive Scout Model for [3, 5, 1, 6, 2, 0, 8, 7, 4] Left Subtree (returns 5) Right Subtree (returns 1) 3 5 1 6 2 0 8 7 4 LCA(5, 1) = 3 LCA(5, 4) = 5 Case A: Diverging Paths → LCA(5, 1) Root 3 sends scouts down both left and right branches. Left scout finds 5; Right scout finds 1. Intersection! Both left & right return non-null. Node 3 instantly recognizes it is the pivot point! Case B: Subtree Containment → LCA(5, 4) Scout enters left subtree and immediately hits 5. Early Return Rule: reports success UPWARD instantly, without needing to explore deeper children like {7, 4}. Target 4 lives inside 5's subtree → Node 5 is LCA! Recursive rule: return node if (cur == p || cur == q || left && right)
Defining LCA in a General Binary Tree via Subtree Intersections diagram
Syntax

Syntax and Python Signatures for Bottom-Up LCA

Phase 3: Syntax and Recursive APIs

To translate our model of subtree intersections into code, we need a clean Python function signature that accepts the current node, along with our targets and . For our tree rooted at 3, we will define a TreeNode class and write a recursive lowest_common_ancestor function that performs a postorder traversal. We check nodes bottom-up, bubbling up non-null return values when a target is found.
python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:
        return root
    return left if left else right
A common syntax and logic mistake when writing this function is forgetting to return root when root == p or root == q. If you omit those equality checks, the traversal will continue past the target node instead of immediately bubbling it up to the parent caller.
python
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # Fix the missing base case below:
    if not root:
        return None
    
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    
    if left and right:
        return root
    return left if left else right
Worked example

Tracing Bottom-Up LCA on the Binary Tree

Phase 4: Tracing Bottom-Up LCA on the Binary Tree

Let us run our recursive postorder function on our locked tree rooted at 3, with left child 5 and right child 1. Node 5 has left child 6 and right child 2 (which itself has children 7 and 4). Node 1 has left child 0 and right child 8.
We will trace LCA(5, 1). The recursive search visits nodes in postorder, returning the node itself if it matches p or q, or bubbling up non-null return values from its left and right subtrees.

Given

- Root node: 3
- Targets: p = 5 and q = 1

Steps

1. dfs(node = 3):
- Calls dfs(left = 5) and dfs(right = 1).
2. dfs(node = 5):
- Since node.val == 5 (which matches p), it immediately returns the node object for 5 without recursing further down its subtree.
3. dfs(node = 1):
- Since node.val == 1 (which matches q), it immediately returns the node object for 1 without recursing down 0 or 8.
4. Back at root 3:
- left returns node 5. right returns node 1. Since both left and right are non-null, root 3 is the lowest common ancestor.
Now consider LCA(5, 4) with targets p = 5 and q = 4:
1. dfs(node = 5) fires first as we descend; it immediately matches p = 5 and returns node 5 upward.
2. Because node 5 returns itself, the recursion short-circuits and does not even explore the subtrees of 6 or 2 (meaning node 4 is never explicitly visited by this specific path branch).
3. The ancestor above receives node 5 from its left branch and null from its right, safely bubbling node 5 all the way to the top.
python
# Execution trace for LCA(5, 4)
def lca(node, p, q):
    if not node or node == p or node == q:
        return node
    left = lca(node.left, p, q)
    right = lca(node.right, p, q)
    if left and right: return node
    return left or right

Result

- LCA(5, 1) = 3 because node 5 is in the left subtree and node 1 is in the right subtree of root 3.
- LCA(5, 4) = 5 because target 5 is an ancestor of target 4, causing the search to return 5 early before ever reaching 4.
python
def trace_lca_step(node, p, q):
    # Trace what happens when node.val == p is encountered early
    pass
Phase 4: Tracing Bottom-Up LCA (Short-Circuit & Return) 3 5 1 6 2 7 4 returns node 5 Never explored! Key Mechanism: Why LCA(5, 4) = 5 Encountering Target p = 5 Early: dfs(node=5) matches p immediately and bubbles up node 5. Short-Circuit & Subtree Pruning: Because node 5 returns itself, recursion never explores nodes 6, 2, 7, or target 4! def lca(node, p, q): if not node or node == p or node == q: return node # <-- returns 5 instantly left = lca(node.left, p, q) right = lca(node.right, p, q) if left and right: return node return left or right # bubbles 5 up safely
Tracing Bottom-Up LCA on the Binary Tree diagram
Practice

Practicing Bottom-Up LCA on a Modified Branch

Phase 5:

Now that you have traced the postorder return values for LCA and LCA in our locked binary tree rooted at 3, let's test your mental execution on a slightly modified variant. Suppose we alter the tree structure such that node 2 has no children, but node 6 now has a left child 9 and right child 10. Your task is to write out or mentally simulate the exact recursive return values for finding in this updated binary tree layout.
Recall the core logic from our syntax and worked phases: if a node equals or , return that node; otherwise, collect left and right non-null returns. Use the Python stub below to complete your mental or scratchpad implementation of this subtree check.
python
def lca_practice(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca_practice(root.left, p, q)
    right = lca_practice(root.right, p, q)
    if left and right:
        return root
    return left if left else right
Walk through what happens when and at node 5: does node 6 bubble up 9, and does node 2 return itself? Trace the values merging at node 5 to find the final intersection point.
python
def lca_practice(root, p, q):
    # TODO: Trace or complete the postorder LCA logic for p=9, q=2
    pass
Edge cases

Navigating Edge Cases and Missing Nodes in LCA

Phase 6: Edge Cases

When writing recursive LCA algorithms for our tree rooted at 3 with children 5 and 1, we must test what happens when our inputs break standard assumptions. In our worked example, we assumed both and always exist within the tree. But what if one or both target nodes are missing entirely? Or what if node 5 is searched alongside node 4, where 5 is an ancestor of 4? Let us look at how the postorder traversal behaves under these failure modes.
First, consider a missing node. If we search for lca(root, 5, 9) where 9 does not exist in the tree , the DFS call inspecting 9 returns None. When the recursion unwinds at the root 3, it receives 5 from the left subtree and None from the right subtree. Following our core rule—if one side is null, return the non-null side—the algorithm returns 5 as the LCA.

Why Returning a Single Non-Null Node is Dangerous

This behavior exposes a major caveat: naive bottom-up LCA assumes both nodes are guaranteed to exist. If node is absent, the algorithm will proudly return node as its own ancestor without warning. To fix this in production code, you either pass a boolean validation flag up the recursion stack or perform a preliminary reachability check to confirm that both and exist in the tree.
Second, consider when one target is an ancestor of the other, such as lca(root, 5, 4). Node 5 is the parent of node 2, which in turn is the parent of node 4. When the traversal hits node 5, it immediately returns node 5 up the call stack because a match for or is found. The left and right subtrees of 5 (including node 2 and node 4) are never independently evaluated to see if 4 triggers a separate branch intersection. Node 5 simply bubbles up, correctly identifying itself as the ancestor of 4.
Apply

Transferring Postorder LCA to Distance and Path Queries

Phase 7: Generalizing Postorder Traversal

We have successfully tracked the postorder traversal of our locked binary tree rooted at 3, finding that LCA(5, 1) returns 3 and LCA(5, 4) returns 5. The core pattern we discovered—bubbling up non-null target references from left and right subtrees—is not locked exclusively to finding ancestors. The exact same recursive descent can be modified to compute distances between nodes, find paths from root to targets, or verify structural properties across arbitrary binary trees.
To see this in action, consider how we transition from finding the LCA of 5 and 4 to finding the exact distance between them. In our locked tree, 5 is the direct parent of 2, and 2 is the parent of 4. While LCA(5, 4) correctly returns 5, we can compute the path length by combining the LCA routine with a path-finding helper or depth tracker.

Extending the Pattern to Pathfinding

When we know the LCA of two nodes, the path between them goes up from the first node to the LCA and then down to the second node. By adapting our postorder state return values, we can extract this entire sequence without running separate top-down searches.

FAQ

What is the LCA of nodes 5 and 4 in the example tree [3,5,1,6,2,0,8] with 2 having children 7 and 4?
The LCA is 5. Because node 5 is an ancestor of node 4 (where 4 is in the left subtree of 2, which is a child of 5), the recursive search bubbles node 5 upward as the first common ancestor.
Why can't we use standard BST search properties for LCA in a general binary tree?
A standard binary tree lacks the ordering property of a BST (where left < root < right). Therefore, we cannot compare node values to decide whether to branch left or right, requiring a full subtree exploration via DFS.
What happens if one of the target nodes is not present in the binary tree?
A standard bottom-up LCA function assumes both nodes exist. If one node is missing, the algorithm may return the present node as a false LCA if it encounters it first without verifying the existence of the second node.
What is the time and space complexity of the bottom-up LCA approach?
The time complexity is O(N) because it visits every node in the binary tree in the worst case. The space complexity is O(H), where H is the height of the tree, consumed by the recursion stack.

Keep learning