Skip to content

Volume ITechnology

4.14.4 — Balanced Binary Tree ​

LeetCode 110 · Easy

The problem ​

You are given the root of a binary tree. Return true if it is height-balanced, and false otherwise. A tree is height-balanced when, at every node, the depths of its left and right subtrees differ by at most 1.

     3
   /   \
  9    20        →  true
      /   \
    15     7

       1
     /   \
    2     2      →  false   (at node 1, the left side has depth 3
   / \                       and the right side has depth 1)
  3   3
 / \
4   4

The tree has up to 5,000 nodes.

What the problem is really asking ​

Two things must be checked at every node:

  1. Is each subtree balanced on its own?
  2. Do the two subtrees' depths differ by at most 1?

The second check needs the depths of both subtrees. So the real question is: can you check balance and compute depths in the same single pass, instead of computing depths over and over?

The brute force, and where it wastes work ​

Check this node, then check both children, computing depths from scratch each time.

python
def isBalanced(root):
    def depth(n):
        return 0 if not n else 1 + max(depth(n.left), depth(n.right))
    if not root:
        return True
    if abs(depth(root.left) - depth(root.right)) > 1:
        return False
    return isBalanced(root.left) and isBalanced(root.right)

It is correct, but slow. The depth call at the root walks the whole tree. Then the root's children call depth again, walking most of the tree again, and so on down. For a tree shaped like a line, that is n + (n - 1) + (n - 2) + \dots, which is about \frac{n^2}{2} steps, or O(n^2).

The waste in one sentence: every subtree's depth is computed again for each of its ancestors, when one bottom-up pass could compute each depth once.

The idea ​

Compute each node's depth once, bottom-up, like 4.14.2. At each node, with both depths in hand, also check the balance rule.

How does a node report "something below me is unbalanced"? Use a sentinel: a special value that can never be a real answer. A real depth is always 0 or more. So we return −1 to mean "unbalanced somewhere down here". Once any node returns −1, every node above it passes the −1 straight up without doing any more work.

This is the "return one thing, record another" idea from 4.14.3, with a twist. Instead of a separate variable, the failure travels inside the return value itself.

The solution ​

python
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def depth(node) -> int:
            if not node:                          # (1)
                return 0

            left = depth(node.left)               # (2)
            if left == -1:
                return -1

            right = depth(node.right)             # (3)
            if right == -1:
                return -1

            if abs(left - right) > 1:             # (4)
                return -1

            return 1 + max(left, right)           # (5)

        return depth(root) != -1                  # (6)
ts
function isBalanced(root: TreeNode | null): boolean {
  function depth(node: TreeNode | null): number {
    if (!node) return 0;                          // (1)

    const left = depth(node.left);                // (2)
    if (left === -1) return -1;

    const right = depth(node.right);              // (3)
    if (right === -1) return -1;

    if (Math.abs(left - right) > 1) return -1;    // (4)

    return 1 + Math.max(left, right);             // (5)
  }

  return depth(root) !== -1;                      // (6)
}

Line by line ​

(1) A missing node has depth 0, and an empty tree is balanced.

(2) Get the left depth. If the left subtree already reported −1, something below is unbalanced. Return −1 at once. Notice that this check comes before we even look at the right side. An unbalanced left subtree means the right subtree is never walked at all.

(3) Get the right depth, with the same early stop.

(4) Check the rule at this node. abs(left - right) is the difference between the two depths, ignoring which is bigger. abs means absolute value: the number without its minus sign, so abs(-2) is 2. If the difference is more than 1, this node breaks the rule.

(5) Balanced here. Return the depth, as in 4.14.2.

(6) The tree is balanced if the root did not report −1.

Why is −1 safe as a sentinel? Because real depths are never negative, so −1 can never be mistaken for an actual depth. When no such spare value exists, use a separate variable instead, as in 4.14.3. Another clear option is returning a pair, (depth, is_balanced). It is a little more code but very explicit. The interviewer cares that you compute each depth once, not which way you report the failure.

Trace ​

Take the second tree, which should be false. Calls finish from the bottom up.

NodeLeft resultRight resultDifferenceReturns
4 (left)0001
4 (right)0001
3 (with two 4s)1102
3 (leaf)0001
2 (left child of 1)2113
2 (right child of 1)0001
1312 > 1−1

The root returns −1, so the answer is false. Every node below the root was fine. Only the root broke the rule.

Complexity, derived ​

Time. Each node's depth is computed exactly once, with constant extra work per node. So O(n). Turning the obvious O(n^2) into O(n) by not recomputing is the whole point of this problem.

Space. The recursion is as deep as the tree is tall, so O(h).

Edge cases ​

  • Empty tree. Balanced. Line (1) gives 0, which is not −1.
  • One node. Balanced.
  • Two nodes, a root with one child. The depths are 1 and 0, a difference of 1. Balanced.
  • Three nodes in a line. At the root, the depths are 2 and 0. Not balanced.
  • Unbalanced deep down but balanced at the root. Caught, because the rule is checked at every node and the −1 is passed upward.

What "balanced" buys you ​

This rule, that every node's two subtree depths are within 1, is exactly what an AVL tree keeps true at all times. An AVL tree is a binary search tree that repairs its own shape after each insert or delete. Keeping it balanced guarantees its height stays about \log_2 n, so searching it takes O(\log n). A binary search tree that is not kept balanced can grow into a long line, and then every search takes O(n). 4.13.2 shows how the repairs work.

Variations you will meet ​

  • Maximum Depth. The same recursion without the check. See 4.14.2.
  • Diameter. The same shape, with a separate variable instead of a sentinel. See 4.14.3.
  • Validate Binary Search Tree. A different rule checked in one pass. See 4.14.11.

The general lesson: when a check at every node needs a value from its subtrees, compute that value once on the way up, and do the check in the same pass.

What the interviewer will push on ​

"Why is the simple version O(n^2)?" Each subtree's depth is recomputed for every ancestor.

"How do you avoid it?" One bottom-up pass that computes each depth once and carries the failure in the return value.

"Why is −1 safe?" Depths are never negative.

"Does balanced mean only at the root?" No, at every node. A tree can be balanced at the root and broken lower down.

One thing to volunteer: mention AVL trees. This rule is not arbitrary. It is the rule a self-balancing tree maintains, and knowing that links the exercise to something real.

Next: 4.14.5 Same Tree. Walking two trees at once, which is the building block for the problem after it.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet