🧠 I Thought I Was Solving Lowest Common Ancestor. I Ended Up Learning Backtracking.

By Sai Pranav Moluguri

Recently, while continuing my DSA journey, I came across a Binary Tree problem:

Lowest Common Ancestor.

At first, the problem sounded simple.

Given two nodes in a binary tree, find their lowest common ancestor.

For example:

a
      /   \
     b     c
    / \     \
   d   e     f
      / \
     g   h

If the two nodes are:

d and h

their lowest common ancestor is:

b

Simple to see.

But when I tried to write the code, I immediately had a question:

Ancestors are above a node. How am I supposed to travel upward when my Node only has left and right pointers?

There is no:

node.parent

That was where the problem became interesting.

The First Idea

Instead of trying to travel upward from a node, I could travel downward from the root.

If I could find the path from the root to both target nodes:

root → ... → val1
root → ... → val2

then the lowest common ancestor should be the last node those two paths have in common.

For the example above:

path to d:

a → b → d

and:

path to h:

a → b → e → h

Compare them:

a → b → d
a → b → e → h
    ↑

a is common.

b is common.

Then the paths diverge at d and e.

So the last common node is:

b

And that’s our lowest common ancestor.

At this point, I thought I understood the problem.

Then I tried to actually build those paths.

And that’s when I learned something much more important than Lowest Common Ancestor.

The Real Problem Was Backtracking

To find a target node, I can perform DFS.

Suppose I’m looking for h.

I start at:

a

So my path becomes:

[a]

Then I explore b:

[a, b]

Then DFS might explore d:

[a, b, d]

But d isn't h.

Now I had a problem.

d is sitting inside my path, even though d isn't actually part of the path from a to h.

This is where backtracking clicked for me.

If I choose a node:

path.append(root.val)

and later discover:

This branch does not lead to my target

then I need to undo that choice:

path.pop()

So:

[a, b, d]
       ↑
    wrong path

becomes:

[a, b]

Then DFS can try another direction.

[a, b, e]

Maybe it tries g:

[a, b, e, g]

Wrong again.

Backtrack:

[a, b, e]

Then try h:

[a, b, e, h]

Found it.

That was the real lesson.

The Backtracking Recipe That Clicked

I started seeing the DFS as three simple operations:

CHOOSE
  ↓
path.append(node)

EXPLORE
  ↓
search children

DIDN'T WORK?
  ↓
UNDO
path.pop()

Or even more simply:

Add → Explore → Not Found → Pop

That pop() isn't some random line at the bottom of a recursive function.

It has meaning.

It says:

“The decision I made at this recursive state did not lead to the solution, so I’m undoing it before returning.”

That changed the way I looked at the recursion.

Every Recursive Call Owns Its Choice

This reminded me of something I learned while studying Dynamic Programming.

In DP, I learned:

Every recursive call owns its own state.

Here I realized something similar:

Every recursive call is responsible for the choice it adds to the path.

If the call succeeds, keep the choice.

If the call fails, undo it.

For example:

DFS(d)

adds:

d

If d doesn't lead to the target, DFS(d) should remove d before returning False.

The parent shouldn’t have to clean up its child’s mistake.

That makes the recursion much easier to reason about.

Another Mistake I Made

Initially, I wrote something like:

if dfs(root.left, node, path):
    return True
else:
    path.pop()
    return False

It looked reasonable.

If the left side doesn’t contain the target, return False.

Except…

What about the right side?

Consider:

e
     / \
    g   h

If I’m searching for h, DFS searches g first.

g returns False.

If I immediately return False, I never even look at:

h

So the correct thinking became:

Am I the target?
        ↓ no

Can LEFT find it?
        ↓ no

Can RIGHT find it?
        ↓ no

Okay.

Neither worked.

NOW undo my current choice
and return False.

That produced this beautiful structure:

if root.val == node:
    return True

if dfs(root.left, node, path):
    return True

if dfs(root.right, node, path):
    return True

path.pop()
return False

The placement of path.pop() matters.

It only happens when:

The current node AND both of its subtrees failed to lead to the target.

That’s backtracking.

Once I Had the Paths, LCA Became Easy

After DFS, I had:

path1 = root → ... → val1
path2 = root → ... → val2

For example:

path1 = [a, b, d]
path2 = [a, b, e, h]

Now I could use two pointers:

i
↓
a → b → d

a → b → e → h
↑
j

Compare:

a == a

Move both.

b == b

Move both.

Then:

d != e

The paths have diverged.

Therefore the node immediately before the divergence:

b

is the lowest common ancestor.

And Then an Old Pattern Appeared Again

There was one more edge case.

Suppose we’re finding the LCA of:

b and h

Their paths are:

a → b
a → b → e → h

We compare:

a == a
b == b

And then the first path ends.

There is no mismatch.

But that’s actually meaningful.

It means:

a → b

is a complete prefix of:

a → b → e → h

Therefore b itself is an ancestor of h.

So:

LCA = b

And suddenly I recognized an old friend.

I’ve seen this same broad idea while solving:

Merge Sort

Process both lists
→ one ends
→ handle what remains

Merge Two Sorted Linked Lists

Process both linked lists
→ one ends
→ attach the remaining list

Lexical Order

Compare both words
→ one ends
→ handle the prefix case

And now:

Lowest Common Ancestor

Compare both root-to-target paths
→ one ends
→ handle the ancestor/prefix case

Different problems.

Same underlying instinct:

If my main loop depends on BOTH sequences existing, I need to ask what it means when one sequence runs out first.

I love when patterns start appearing across completely different problems.

My Recipe for This Problem

If I had to solve this again from scratch, this is the recipe I would follow:

1. Perform DFS to find the path from the root to the first target.
2. Perform DFS again to find the path from the root to the second target.
3. During DFS, if root is None, return False.
4. Add the current node to the path.
5. If the current node is the target, return True.
6. Search the left subtree.
7. If left doesn’t find it, search the right subtree.
8. If neither subtree finds the target, pop() the current node and return False.
9. Now compare both root-to-target paths from the beginning.
10. While values are equal, move both pointers.
11. At the first mismatch, the previous value is the Lowest Common Ancestor.
12. If one path ends before a mismatch, the final matching value is the ancestor.

But the recipe I really want to remember is much smaller:

CHOOSE
↓
ADD

EXPLORE
↓
DFS

FAIL?
↓
UNDO

path.pop()

That’s backtracking.

My Final Solution

# class Node:
#   def __init__(self, val):
#     self.val = val
#     self.left = None
#     self.right = None

def lowest_common_ancestor(root, val1, val2):
  path1, path2 = [], []

  dfs(root, val1, path1)
  dfs(root, val2, path2)

  i, j = 0, 0

  while i < len(path1) and j < len(path2):
    if path1[i] == path2[j]:
      i += 1
      j += 1
    else:
      return path1[i - 1]

  if i == len(path1):
    return path1[i - 1]

  if j == len(path2):
    return path2[j - 1]

def dfs(root, node, path):
  if root is None:
    return False

  path.append(root.val)

  if root.val == node:
    return True

  if dfs(root.left, node, path):
    return True

  if dfs(root.right, node, path):
    return True

  path.pop()
  return False

My Takeaway

I started this problem thinking I was learning how to find the Lowest Common Ancestor in a Binary Tree.

I did learn that.

But that wasn’t the part I want to remember.

The bigger lesson was:

When recursion makes a choice, explores that choice, and discovers that the choice doesn’t lead to the solution, undo the choice before returning.

Choose.
Explore.
Fail.
Undo.

Choose.
Explore.
Fail.
Undo.

Choose.
Explore.
Found it.
Keep it.

That’s backtracking.

And now path.pop() means something completely different to me.

It’s not merely removing the last element of a Python list.

It’s saying:

“This branch wasn’t part of my answer. Undo my decision and try another path.”

Those are the moments I enjoy most in DSA.

I might begin with one problem.

But somewhere between the wrong code, the dry runs, the recursion, and finally getting it to work, I discover a reusable way of thinking.

And that is worth much more than memorizing another solution.

“With great power, there must also come great responsibility.”

Forever Learning. Forever Growing.

— Sai Pranav Moluguri