Skip to main content

The LCA Revelation: When Return Values Tell a Story

· 20 min read
Mahmut Salman
Mahmut Salman
Software Developer

A conversation about solving the Lowest Common Ancestor problem that reveals one of the most elegant patterns in tree recursion—using return values to communicate information upward through the call stack.

The Problem​

Teacher: Today we're tackling a classic tree problem that appears in almost every technical interview. Let me show you the Lowest Common Ancestor problem:

Problem: Lowest Common Ancestor of a Binary Tree

Return the lowest common ancestor (LCA) of two nodes, p and q, in a binary tree. The LCA is defined as the lowest node that has both p and q as descendants. A node can be considered an ancestor of itself.

Example:

        1
       / \
      2   3
     /\   /\
    4  5 6  7
         /\
        8  9

Input: p = 8, q = 7
Output: 3 (LCA is node 3)

Explanation: Node 3 is the lowest ancestor that has
both 8 and 7 as descendants.

Constraints:

  • The tree contains at least two nodes
  • All node values are unique
  • p and q represent different nodes in the tree
  • Both p and q exist in the tree ⚠️ (This is crucial!)

My Initial Confusion​

Me: Alright, I'm looking at this problem. First thing that came to my mind is... I don't know which data structure to use.

But I know that it depends on what I need. But what do I need in this question?

I know it sounds silly, but recognizing what one needs is essential towards solving a problem.

My first thought was that each node can have some sort of list that holds its children and I can check... but hold on, this won't work.

I know:

  • This is a tree question
  • I know DFS
  • I know essentials of recursion
  • I know how to use parameters of a recursive function
  • I know how to have a list outside of a recursive function to record the process (like memory)

But here I can't see a clear path. Don't give me the solution yet - guide me instead!

Teacher: Excellent self-awareness! You're right - knowing what you need is half the battle. Let's start by clarifying exactly what we're looking for.

Understanding the Goal​

Me: For this problem, I need to reach to p and q. That's one thing. Finding them is one job.

After finding, I need to know their parents. And among parents, I should return the first one, the closest one.

I'm not sure if this logic is correct or not.

While trying to find them, I can record all the nodes I come across. I can do this for both nodes. After finding all the path nodes (the nodes that I come across until reaching that node), I need to compare those two lists.

Teacher: That's actually one valid approach! Recording paths to both nodes and then finding their intersection would work. But before we commit to that, let me ask you some guiding questions to see if we can find something more elegant.

Question 1: What Makes a Node the LCA?​

Teacher: Looking at the example where p=8 and q=7, what is their LCA and why? Walk me through your reasoning.

Me: Let me look at the tree:

        1
       / \
      2   3  ← This is the LCA
     /\   /\
    4  5 6  7 (q)
         /\
        8  9
       (p)

Node 3 is the LCA because:

  • It has 8 in its left subtree (through node 6)
  • It has 7 as its right child
  • It's the lowest/deepest node that has both as descendants

Teacher: Perfect! Now think about this pattern:

When you're standing at a node in the tree (let's say node 3), what would make that node the LCA of p and q?

There are only two scenarios where a node can be the LCA:

  1. The node itself is one of p or q, and the other one is somewhere in its subtree
  2. The node has p in one subtree and q in another subtree

Can you see why these are the only two cases?

Me: Hmm... let me think:

Case 1: If I'm at node 6, and node 8 (which is p) is below me, and I myself could be q, then I'm the LCA.

Case 2: If I'm at node 3, and I have p somewhere in my left subtree and q somewhere in my right subtree (or vice versa), then I'm the LCA.

Yes! These are the only possibilities!

Question 2: Information Flow in Recursion​

Teacher: Great! Now, about your path recording idea:

Your approach of recording paths could work! But consider this:

When we do DFS traversal recursively, information naturally flows upward from children to parents as the recursion unwinds.

What if, instead of recording entire paths, each recursive call could just tell its parent:

  • "Hey, I found p!"
  • "Hey, I found q!"
  • "Hey, I found both (the LCA)!"

Think about: What's the minimum information that each node needs to know from its children to determine if it's the LCA?

Me: Hmm... each node just needs to know:

  • Did my left child find p or q (or their LCA)?
  • Did my right child find p or q (or their LCA)?

If both children found something, then I'm the LCA!

If only one child found something, I just pass that information upward...

Teacher: Exactly! Now you're thinking recursively! 🎯

The Elegant Solution​

Me: Alright, now give me the full answer in Java!

Teacher: I notice you're jumping straight to the solution! But since you asked, let me provide it with detailed explanation of the key insight:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if we reach null or find either p or q
        if (root == null || root == p || root == q) {
            return root;
        }

        // Search in left and right subtrees
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // KEY INSIGHT: What does each return value mean?
        // - If left is not null: we found p or q (or their LCA) in left subtree
        // - If right is not null: we found p or q (or their LCA) in right subtree

        // Case 1: Both sides found something -> current node is the LCA!
        if (left != null && right != null) {
            return root;
        }

        // Case 2: Only one side found something -> propagate it upward
        return (left != null) ? left : right;
    }
}

Complexity:

  • Time: O(n) - visit each node at most once
  • Space: O(h) - recursion stack depth where h is height

The Key Pattern​

Teacher: The breakthrough insight is that we're using the return value to communicate information upward. Each recursive call answers:

"Did I find p, q, or their LCA in my subtree?"

Think about what happens:

  1. When we find p or q, we immediately return it
  2. That node bubbles up through the recursion
  3. The first node that gets non-null returns from BOTH children must be the LCA
  4. If only one child returns non-null, we just pass that up (it could be the LCA from deeper in the tree)

Why This Works​

If p is an ancestor of q (or vice versa):

  • We return p immediately when we find it
  • q never gets returned separately
  • p itself is the LCA

If p and q are in different subtrees:

  • They bubble up separately until they meet at their LCA
  • The first common ancestor receives both as non-null returns

The elegance here is that we're solving three problems simultaneously:

  1. Finding p
  2. Finding q
  3. Determining their LCA

All through a single traversal with clever use of return values!

My First Question: The Constraint​

Me: The part I didn't get about this question is:

I see that if left and right TreeNode are not null, then it means we have information that we have both p and q nodes.

But what if one of them or none of them is found? What should I return?

I guess in the question it's said that p and q exist absolutely, right?

Teacher: Excellent observation! You've hit on a critical point that many people miss.

Yes, you're absolutely right - the problem guarantees that both p and q exist in the tree, and this guarantee is essential for our solution to work correctly.

Why the Constraint Matters​

Teacher: Let's break down what happens in each scenario:

When we return (left != null) ? left : right:​

This line handles multiple cases:

  1. Only found one node (p OR q) in entire subtree:

    • We bubble that node up, hoping the other one will be found elsewhere

  2. Found the LCA deeper in the subtree:

    • If the LCA was already determined in a deeper recursive call (like when p is ancestor of q)
    • We're just propagating that answer upward

  3. Found nothing:

    • Both left and right are null
    • So we return null upward

Why the guarantee matters​

If the problem didn't guarantee both nodes exist, our algorithm could incorrectly return:

  • Just p (if q doesn't exist)
  • Just q (if p doesn't exist)
  • null (if neither exists)

And we wouldn't know if we're returning a single node because:

  • It's the LCA (ancestor of the other)
  • OR the other node doesn't exist!

Example of the Problem​

Think about this scenario:

       1
      / \
     2   3
    /
   4 (p)

If we search for p=4 and q=999 (doesn't exist):

  • Our algorithm would return 4
  • But that's not really an LCA - it's just the only node we found!

So yes, the constraint "p and q represent different nodes in the tree" is crucial:

  • ✅ We'll always find both nodes
  • ✅ We'll always have a valid LCA
  • ✅ Our return value has clear meaning: either "found one/both" or "found nothing yet"

Teacher: This is a great example of why problem constraints aren't just limitations - they're part of the solution design!

My Second Insight: The Two Parts Working Together​

Me: I think these two parts are working together:

if (left != null && right != null) {
    return root;
}

// Case 2: Only one side found something -> propagate it upward
return (left != null) ? left : right;

Because without the second return part where we return left or right conditionally, our code wouldn't work!

Let's say we find LCA and now we need to bubble this upward. But by returning root there, we bubble up only one time. But we can be in a deep position and we need to carry this until the initial root node.

To be able to do that, we need something like return (left != null) ? left : right; to take it from the parent node and again bubble upward.

Currently, the part I fully understood is only the part where we find something from both left and right subtrees and this makes the current node LCA, and we return root. I get this fully.

But Case 2, I think I don't have enough thought process and understanding for it. Guide me and help me see why we need that.

We have a beautiful base case too. As soon as we reach p or q, we immediately return. So we don't go any deeper than that. This is quite logical - we don't make unnecessary recursive calls.

But this is a bit unclear to me still. Like we are returning p or q when we find them. And in parent nodes, we check if children return p or q or both.

Hmm... I see it actually. Quite understandable!

Teacher: Brilliant! You're having a real breakthrough moment here! 🎉

The Complete Trace-Through​

Teacher: You've correctly identified that these two parts work together - one finds the LCA, the other propagates it upward. Let me help solidify your understanding with a concrete trace-through.

Let's trace through your example (p=8, q=7):

       1
      / \
     2   3
    /\   /\
   4  5 6  7(q)
       /\
      8  9
     (p)

Bottom-Up Execution Flow​

At node 8:

root == p  // true!
return 8   // We found p!

At node 9:

root == null  // (no left or right children)
return null

At node 6:

left = lowestCommonAncestor(6.left)   // returns 8 (that's p!)
right = lowestCommonAncestor(6.right) // returns 9? No, null

left != null && right != null?  // false (right is null)
return (left != null) ? left : right
return 8  // Propagating p upward

At node 7:

root == q  // true!
return 7   // We found q!

At node 3 (THE CRITICAL MOMENT):

left = lowestCommonAncestor(3.left)   // returns 8 (p propagated up!)
right = lowestCommonAncestor(3.right) // returns 7 (q!)

left != null && right != null?  // TRUE! Both found!
return root  // This is the LCA! Return node 3

At node 2:

left = lowestCommonAncestor(2.left)   // returns null
right = lowestCommonAncestor(2.right) // returns null

left != null && right != null?  // false
return (left != null) ? left : right
return null  // Nothing found in this subtree

At node 1:

left = lowestCommonAncestor(1.left)   // returns null (from node 2)
right = lowestCommonAncestor(1.right) // returns 3 (the LCA!)

left != null && right != null?  // false (left is null)
return (left != null) ? left : right
return 3  // Propagating the LCA upward

Final answer: 3 ✓

Visual Call Stack​

Let me show you the call stack visually:

Call Stack (Going Down):
lca(1) → lca(2) → lca(4) → returns null
              ↓
           lca(5) → returns null

      → lca(3) → lca(6) → lca(8) → returns 8 ⭐ (found p!)
                        ↓
                     lca(9) → returns null
              ↓
           lca(7) → returns 7 ⭐ (found q!)

Return Flow (Bubbling Up):
lca(8) returns 8
       ↓
lca(6) receives: left=8, right=null → returns 8 (propagate)
       ↓
lca(7) returns 7
       ↓
lca(3) receives: left=8, right=7 → returns 3 ⭐ (LCA found!)
       ↓
lca(1) receives: left=null, right=3 → returns 3 (propagate)
       ↓
Final answer: 3

The Key Insight: Dual Role of Return​

Teacher: The return (left != null) ? left : right serves two different purposes:

Before LCA is found:​

It propagates individual nodes (p or q) upward

At node 6:
- Found 8 in left subtree
- Return 8 upward (propagating p)

After LCA is found:​

It propagates the LCA itself upward

At node 1:
- Right child returned 3 (the LCA)
- Return 3 upward (propagating the answer)

Think of it like a relay race:

  • Each node is a runner
  • They're passing a baton (the found node or LCA)
  • The baton keeps going up until it reaches the finish line (root of tree)

Why Can't We Just Return Root Everywhere?​

Me: You asked a great question earlier! If we returned root instead of propagating what we found, look what would happen:

Wrong approach:

if (left != null && right != null) {
    return root;  // Find LCA
}
// Missing the propagation!
return root;  // This would be wrong!

What would happen:

  • At node 6: We'd return 6 (wrong! We should pass up 8)
  • At node 3: We'd correctly identify it as LCA ✓
  • At node 1: We'd return 1 (wrong! We should pass up 3)

The propagation ensures that once we find something important (p, q, or their LCA), that information makes it all the way back to the original caller!

Complete Implementation​

Here's the complete solution with detailed comments:

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case 1: Reached null (end of a path)
        if (root == null) {
            return null;
        }

        // Base case 2: Found one of the target nodes
        // No need to go deeper - if the other node is below this one,
        // this node IS the LCA (case where one is ancestor of other)
        if (root == p || root == q) {
            return root;
        }

        // Recursive case: Search both subtrees
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q);

        // Analysis of what children reported:

        // Case 1: Both subtrees found something
        // This means p is in one subtree and q is in the other
        // Therefore, current node is the LCA!
        if (leftResult != null && rightResult != null) {
            return root;
        }

        // Case 2: Only left subtree found something
        // Could be p, q, or the LCA from deeper in the tree
        // Propagate it upward
        if (leftResult != null) {
            return leftResult;
        }

        // Case 3: Only right subtree found something
        // Same as Case 2, but from right side
        if (rightResult != null) {
            return rightResult;
        }

        // Case 4: Neither subtree found anything
        // This entire subtree doesn't contain p or q
        return null;
    }
}

Simplified version:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // Base cases
    if (root == null || root == p || root == q) {
        return root;
    }

    // Search both subtrees
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    // Both found -> LCA is here
    if (left != null && right != null) {
        return root;
    }

    // Propagate non-null result upward
    return (left != null) ? left : right;
}

Testing the Solution​

public class TestLCA {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Build example tree:
        //        1
        //       / \
        //      2   3
        //     /\   /\
        //    4  5 6  7
        //         /\
        //        8  9

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.left.left = new TreeNode(8);
        root.right.left.right = new TreeNode(9);

        // Test case 1: p=8, q=7
        TreeNode p1 = root.right.left.left;   // node 8
        TreeNode q1 = root.right.right;       // node 7
        TreeNode lca1 = sol.lowestCommonAncestor(root, p1, q1);
        System.out.println("LCA(8, 7) = " + lca1.val);  // Expected: 3

        // Test case 2: p=4, q=5
        TreeNode p2 = root.left.left;   // node 4
        TreeNode q2 = root.left.right;  // node 5
        TreeNode lca2 = sol.lowestCommonAncestor(root, p2, q2);
        System.out.println("LCA(4, 5) = " + lca2.val);  // Expected: 2

        // Test case 3: p=2, q=8 (one is ancestor of other)
        TreeNode p3 = root.left;                // node 2
        TreeNode q3 = root.right.left.left;     // node 8
        TreeNode lca3 = sol.lowestCommonAncestor(root, p3, q3);
        System.out.println("LCA(2, 8) = " + lca3.val);  // Expected: 1

        // Test case 4: p=6, q=8 (parent-child relationship)
        TreeNode p4 = root.right.left;          // node 6
        TreeNode q4 = root.right.left.left;     // node 8
        TreeNode lca4 = sol.lowestCommonAncestor(root, p4, q4);
        System.out.println("LCA(6, 8) = " + lca4.val);  // Expected: 6
    }
}

Output:

LCA(8, 7) = 3
LCA(4, 5) = 2
LCA(2, 8) = 1
LCA(6, 8) = 6

Common Mistakes​

❌ Mistake 1: Not Handling the "One is Ancestor" Case​

// Wrong: Continues searching even after finding p or q
if (root == null) {
    return null;
}

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);

// Missing the base case!
if (root == p || root == q) {
    return root;  // Should be checked BEFORE recursing!
}

Why it's wrong: If p is an ancestor of q, we'd recurse into p's subtree and miss the fact that p itself is the LCA.

Correct: Check root == p || root == q before making recursive calls.

❌ Mistake 2: Forgetting to Propagate​

// Wrong: Doesn't propagate found nodes/LCA upward
if (left != null && right != null) {
    return root;
}
// Missing: return (left != null) ? left : right;
return null;  // Loses the information!

Why it's wrong: The found nodes or LCA would never make it back to the root caller.

❌ Mistake 3: Only Returning When Both Are Found​

// Wrong: Only returns when LCA is found
if (left != null && right != null) {
    return root;
}
return null;  // Loses individual p or q!

Why it's wrong: When we find just p or q, we need to propagate that information upward so a higher ancestor can determine the LCA.

❌ Mistake 4: Not Understanding the Return Value Meaning​

// Confused logic - treating return value as boolean
if (left == p || left == q) {  // Wrong comparison!
    // ...
}

Why it's wrong: The return value isn't telling us specifically which node was found - it's passing the actual node reference upward.

❌ Mistake 5: Assuming Both Nodes Must Be Leaf Nodes​

// Wrong assumption: only checking leaves
if (root.left == null && root.right == null) {
    if (root == p || root == q) {
        return root;
    }
}

Why it's wrong: p or q can be any node in the tree, including internal nodes!

Alternative Approach: Path Recording​

Teacher: Remember your initial idea about recording paths? Let's see how that would work:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathToP = new ArrayList<>();
        List<TreeNode> pathToQ = new ArrayList<>();

        // Find path to p
        findPath(root, p, pathToP);

        // Find path to q
        findPath(root, q, pathToQ);

        // Find last common node in both paths
        TreeNode lca = null;
        int minLen = Math.min(pathToP.size(), pathToQ.size());

        for (int i = 0; i < minLen; i++) {
            if (pathToP.get(i) == pathToQ.get(i)) {
                lca = pathToP.get(i);
            } else {
                break;
            }
        }

        return lca;
    }

    private boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) {
            return false;
        }

        path.add(root);

        if (root == target) {
            return true;
        }

        if (findPath(root.left, target, path) ||
            findPath(root.right, target, path)) {
            return true;
        }

        path.remove(path.size() - 1);  // Backtrack
        return false;
    }
}

Complexity:

  • Time: O(n) - still need to traverse the tree twice
  • Space: O(h) for each path, so O(h) total

Comparison:

AspectElegant SolutionPath Recording
Traversals12 (one for each node)
SpaceO(h) recursionO(h) for paths + O(h) recursion
ClarityMore elegant once understoodMore intuitive initially
InterviewShows deep understandingSafe fallback approach

Both work! But the elegant solution shows mastery of recursion.

Key Takeaways​

What We Learned

  1. Return Values as Communication:

    • In tree recursion, return values can carry information upward
    • Each node receives reports from its children and makes decisions

  2. The Two LCA Cases:

    • Case 1: One node is ancestor of the other
    • Case 2: Nodes are in different subtrees

  3. Dual Role of Propagation:

    return (left != null) ? left : right;
    • Before LCA found: Propagates individual nodes (p or q)
    • After LCA found: Propagates the LCA itself

  4. Base Case Optimization:

    if (root == p || root == q) return root;
    • Stop searching when we find target
    • Handles "one is ancestor" case elegantly

  5. Critical Constraint:

    • Problem guarantees both nodes exist
    • Essential for our return value logic to work correctly

  6. Information Flow Pattern:

    Find node → Return it → Propagate upward →
    Meet at LCA → Identify LCA → Propagate answer

  7. When to Use Each Approach:

    • Elegant solution: When you understand recursion deeply
    • Path recording: When you need a more intuitive approach
    • Both are valid! Choose based on comfort level

  8. The Relay Race Analogy:

    • Nodes are runners passing a baton (found node/LCA)
    • Baton travels upward through return values
    • First node receiving batons from both sides wins (is the LCA)

Similar Problems​

Try these to solidify your understanding:

  1. Binary Tree Maximum Path Sum - Similar propagation pattern
  2. Lowest Common Ancestor of a BST - Can optimize using BST properties
  3. Distance Between Nodes in Binary Tree - Uses LCA as foundation
  4. Kth Ancestor of a Tree Node - Related ancestor-finding problem

Tags: #algorithms #binary-trees #recursion #dfs #lowest-common-ancestor #learning-journey #interview-prep

The Learning Journey​

Teacher: So what did we discover today?

Me: That return values in recursion can tell a story!

I learned:

  • The two cases where a node can be the LCA
  • How to use return values to propagate information upward
  • The beautiful dual role of the propagation logic
  • Why problem constraints matter (both nodes must exist!)
  • The importance of understanding the "relay race" of information flow

The most important insight was understanding that:

return (left != null) ? left : right;

This single line handles multiple scenarios:

  • Propagating individual nodes upward before LCA is found
  • Propagating the LCA itself once it's determined
  • Returning null when nothing is found

Teacher: Exactly! And here's the beautiful part:

This pattern of using return values to communicate information upward through recursion appears in many tree problems:

  • Maximum path sum
  • Diameter of binary tree
  • Balanced tree checking
  • Subtree problems

Once you see this pattern, you'll recognize it everywhere!

The key insight is: Each node makes a local decision based on what its children report, then reports upward to its parent.

It's like a company hierarchy - each manager makes decisions based on reports from their team, then reports to their own manager!

This conversation happened during a real learning session. Sometimes the most elegant solutions come from understanding that recursion isn't just about going down—it's also about the information flowing back up through return values!