Leetcode Sunday #2

LeetCode 110: Balanced Binary Tree

Difficulty: Easy

Time Spent: ~3 hours

This was one of those problems that reminded me why difficulty labels can be misleading. What initially looked like a straightforward tree check turned into a deep lesson on recursion, abstraction, and problem framing.

The problem statement was short and deceptively simple:

A binary tree is balanced if the heights of the left and right subtrees of every node differ by no more than 1.

Given a binary tree, determine if it is height-balanced, and that was it.

That single sentence hides the real challenge.

---

My Initial Misinterpretation

My first instinct was to think in terms of values rather than structure.

I initially reasoned along these lines:

• Check the left and right nodes
• Compare some “minimum” and “maximum”
• If the difference is <= 1, return true; otherwise false
• Done ✔️

But something felt off.

Despite passing some cases, I kept failing others. That was the signal that my mental model of the problem was wrong.

---

The Key Realization

The breakthrough came when I realized this:

Tree balance has nothing to do with node values.

It is purely about height.

Once that clicked, my first approach was completely invalidated.

---

Why This Is a Height Problem

For every node in the tree, you must ask:

• What is the height of my left subtree?
• What is the height of my right subtree?
• Is the difference between them more than 1?

If any node violates this rule, the entire tree is unbalanced.

This immediately suggests a recursive solution, but designing the recursion correctly is where things get interesting.

---

The First Recursive Attempt (And Why It Failed)

I started with this idea:

func isBalanced(node *TreeNode) bool {
    if node == nil {
        return true
    }

    left := isBalanced(node.Left)
    right := isBalanced(node.Right)

    // ... now what?
}

I quickly hit a wall.

The Problem With Returning bool

At each node, I actually need two pieces of information:

• Is my subtree balanced?
• What is the height of my subtree?

A bool can only answer the first question.

Once you commit to returning bool, you lose access to height information higher up the recursion. This makes isBalanced a poor abstraction for this problem, at least one that I could use to create my solution.

---

Designing a Better Recursive Contract

Instead of returning only whether a subtree is balanced, I decided to return more information.

That led to a key insight:

A recursive function can encode multiple meanings into its return value.

---

The Sentinel-Value Trick (Almost Right)

I introduced a helper function:

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := height(node.Left)
    right := height(node.Right)

    if left == -1 || right == -1 {
        return -1
    }

    if (left-right) < 0 {
        return 0
    } else if (left-right) > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

The Idea

• If the subtree is balanced, return its height
• If the subtree is unbalanced, return -1
• Since height can never be negative, -1 becomes a clear sentinel value
• Once -1 appears, it propagates upward and short-circuits the recursion

This is a powerful pattern.

Unfortunately… my logic was still flawed.

---

The Bug: Direction vs Distance

I made a dangerous assumption:

“If left - right is negative, that’s fine.”

That assumption is wrong.

A negative value only tells you direction, not magnitude.

• -1 → acceptable
• -5 → absolutely not acceptable

By not accounting for absolute difference, I implicitly assumed the right subtree was always taller in a “safe” way.

This caused a failure on the test case:

[1, null, 2, null, 3]

Visualizing the Problem

    1
     \
      2
       \
        3

What Should Happen

height(3) = 1
height(2) = 2
height(1) → detects imbalance → returns -1

What Actually Happened

height(3) = 1
height(2) = 2
height(1) sees left-right = -2 → returns 0

Returning 0 incorrectly marked the tree as balanced.

---

The Fix: Absolute Difference

The correct balance condition is:

-1 <= left - right <= 1

Which is much clearer and safer when expressed as:

abs(left - right) <= 1

Once I made that change, everything on the check was smiling green.

---

The Final Solution

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return height(root) != -1
}

func height(node *TreeNode) int {
    if node == nil {
        return 0
    }

    left := height(node.Left)
    right := height(node.Right)

    if left == -1 || right == -1 {
        return -1
    }

    if int(math.Abs(float64(left-right))) > 1 {
        return -1
    }

    if left > right {
        return left + 1
    }
    return right + 1
}

---

What This Problem Actually Taught Me

• How to design better recursive contracts
• Why sentinel values are powerful
• Why correctness often beats premature optimisation
• Why tree problems are more about information flow than traversal

---

Final Thoughts

This problem took me around three hours, not because it was hard to code, but because it forced me to rethink how recursion communicates information.

Tree recursion isn’t about memorising patterns.

It’s about understanding what each node needs to know and what it must pass upward.

If this problem confused you at first, that’s a good sign. That confusion is where real understanding begins.