DSA sheet · Trees · DFS pattern

Balanced Binary Tree

This problem is really the definition of a balanced tree turned into code. The teacher first solves it with BFS (measure the heights again for every node, O(n²)), then with DFS (get the heights from below in one pass, O(n)). On the way she writes a DFS that looks right but gives a wrong answer, shows the example that breaks it, and fixes it. That fix, "once a subtree says −1, pass −1 straight up", is the main lesson. The DFS is almost the same as Diameter of Binary Tree, so read that first if you haven't.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Words you must know first
• Part A · Balanced check with BFS (brute force, O(n²))
• Part B · DFS, first try (has a bug)
• Part C · DFS, fixed (optimal, O(n))
• Part D · Revision page

Part 0 · Words you must know first

Part A · Balanced check with BFS (brute force)

LeetCode 110

1The question in simple words

Given the root of a binary tree, return True if it is height-balanced, otherwise False.

      1
     / \
    2   3
       / \
      4   5

      1
     / \
    2   6
     \
      3
       \
        4
         \
          5

• Example 1: at node 1, left height = 1 (just 2), right height = 2 (3, then 4/5). Gap 1 → fine. At 3: 1 vs 1 → fine. Leaves: 0 vs 0 → fine. So True.
• Example 2: at node 3 (circled), left height = 0, right height = 2 (4 → 5). Gap 2 → False. One bad node is enough. (The teacher's second example is the chain 1 → 2 → 3 → 4 → 5. We added leaf 6 on 1's right so we can later show that the right side gets skipped.)

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

2What the constraints tell us

• Number of nodes: 0 to 5000 → 0 is allowed. So even the BFS version needs a base case: an empty tree counts as balanced → return True. (In the earlier problems n started at 1, so BFS could skip this.)
• In DFS the base case is needed no matter what the constraints say: recursion keeps going down until it hits None, and the base case is the only thing that stops it.
• n ≤ 5000 → n² = 25 × 10⁶. That is below 10⁸, so even the O(n²) BFS will be accepted, just slowly.

3Intuition

Stand on a node. To judge it, you need two numbers: how tall is my left side, how tall is my right side. If the gap is more than 1, stop and say False. Do this for every node. If nobody fails, say True.

The BFS way: visit nodes level by level with a queue. For each one, call a helper that measures height by counting levels (a level-order traversal, the same helper as in Diameter).

4Building the logic

• Pop a node. left = height(node.left), right = height(node.right).
• If abs(left - right) > 1 → return False right away. One bad node ruins the whole tree, so there's no reason to check the rest.
• Otherwise this node is fine. Push its children that exist so they get checked too.
• If the queue empties without any False, every node passed → return True.

5Approach steps

1. If root is None → return True.
2. Put the root in a queue.
3. While the queue isn't empty: pop a node, measure the left and right heights with a level-order count.
4. If the gap is more than 1 → return False.
5. Push the existing children.
6. After the loop → return True.

6Code (Python)

from collections import deque

class Solution:
    def isBalanced(self, root):
        if root is None:                       # 0 nodes is allowed
            return True
        queue = deque([root])
        while queue:
            node = queue.popleft()
            left = self.height(node.left)
            right = self.height(node.right)
            if abs(left - right) > 1:          # this node is lopsided
                return False
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return True                            # nobody failed

    def height(self, root):                    # count levels, store nothing
        if root is None:
            return 0
        queue = deque([root])
        height = 0
        while queue:
            for _ in range(len(queue)):        # one full level
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            height += 1
        return height

7Code line by line

8Dry run: Example 1

On Example 2: pop 1 → height(2) = 4, height(6) = 1 → gap 3 → False straight away.

9Complexity & remember

• Time O(n²): the outer loop visits n nodes. For each, the helper walks the left part (about n/2) and the right part (about n/2), so about n work per node → n × n. With n = 5000 that's 25 × 10⁶: accepted but slow. If it ever went past about 10⁸, TLE would be likely.
• Space O(2n) → O(n): the outer queue plus the helper's own queue.

Part B · DFS, first try (has a bug)

1The question (same as Part A)

Same check, same examples. We want one pass instead of re-measuring.

2Constraints

Same as Part A. The base case (None) is a must in DFS for two reasons, as the teacher stresses: the tree itself can be empty, and the recursion will always reach a None child at the bottom.

3Intuition

A node can't be judged until it knows both heights, so go deep first and decide on the way back up (left, right, then the node). Each child returns its height to its parent, exactly like in Diameter. So we never re-measure a subtree.

The new problem: how does a node say "I failed"?

The function returns a height, which is a number. When a node finds a gap > 1, it wants to say "False", but the parent is waiting for a number to compare. So we need a number that means False.

Heights are always 0, 1, 2, … (never negative). So any negative number can't be confused with a real height. The teacher picks −1 to mean "not balanced". (−2 or any negative would also work.) At the very end, the main function turns it back into a boolean: height(root) != -1.

4Building the logic

• Base case: None → return 0. Why 0 and not just return? The parent subtracts the two heights. With 0, a leaf like 2 gets left 0, right 0, gap 0 → balanced, which is right.
• Get left and right from the two recursive calls.
• If abs(left - right) > 1 → return −1 (we can't return False here, the return type is a number).
• Otherwise return the height: think of node 3 in Example 1. Its sides are 1 and 1. Its parent wants the taller side plus 3 itself → max(left, right) + 1 = 2.

5Approach steps

1. isBalanced(root) returns height(root) != -1.
2. In height(node): None → 0.
3. Get left and right heights.
4. Gap > 1 → −1. Else → max(left, right) + 1.

6Code (Python), the buggy version

class Solution:
    def isBalanced(self, root):
        return self.height(root) != -1

    def height(self, root):
        if root is None:
            return 0
        left = self.height(root.left)
        right = self.height(root.right)
        if abs(left - right) > 1:
            return -1                      # "not balanced"
        return max(left, right) + 1

7Code line by line

8Dry run: it works on Example 1, fails on Example 2

Example 1 (works)

1. h(1) → h(2) → h(None) = 0 and h(None) = 0. Gap 0 → h(2) returns 1.
2. h(1) goes right: h(3) → h(4): leaf → 1. h(5): leaf → 1.
3. h(3): 1 vs 1 → gap 0 → returns 1 + 1 = 2.
4. h(1): 1 vs 2 → gap 1, fine → returns 2 + 1 = 3.
5. 3 != −1 → True ✓

Example 2 (fails!)

1. Calls go 1 → 2 → (2 has no left: 0) → 3 → (3 has no left: 0) → 4 → (4 has no left: 0) → 5.
2. h(5): leaf → 1.
3. h(4): left 0, right 1 → gap 1, fine → returns 2.
4. h(3): left 0, right 2 → gap 2 → returns −1. Good, it noticed.
5. h(2): left 0, right −1. Gap = abs(0 − (−1)) = 1 → "fine"?! Returns max(0, −1) + 1 = 1. The −1 has disappeared.
6. h(1): left 1, right h(6) = 1 → gap 0 → returns 2.
7. 2 != −1 → True ✗. Expected False.

9Complexity & remember

O(n) time, but wrong, so it doesn't matter yet. Never mix a signal value with real values without checking it first.

Part C · DFS, fixed (optimal)

1The question and 2 constraints

Same as before. Nothing changes here.

3Intuition: what changes from Part B

If a child already said "not balanced", the whole tree is not balanced. There's nothing left to measure. So the moment a call gets −1 from a child, it returns −1 at once, before doing any abs() or max(). The −1 then travels straight up to the top.

4Building the logic: two new lines

• Right after getting left: if left == -1: return -1. The teacher's point: if the left side has already failed, why even go to the right side? Skip it.
• Right after getting right: if right == -1: return -1.
• Only when both are real heights do we check the gap and return max + 1.

5Approach steps

1. None → 0.
2. left = height(left child). If −1 → return −1.
3. right = height(right child). If −1 → return −1.
4. If abs(left − right) > 1 → return −1.
5. Return max(left, right) + 1.
6. Main: return height(root) != -1.

6Code (Python)

class Solution:
    def isBalanced(self, root):
        return self.height(root) != -1

    def height(self, root):
        if root is None:                   # empty tree / bottom of recursion
            return 0
        left = self.height(root.left)
        if left == -1:                     # left already failed: stop
            return -1
        right = self.height(root.right)
        if right == -1:                    # right already failed: stop
            return -1
        if abs(left - right) > 1:          # this node is lopsided
            return -1
        return max(left, right) + 1        # real height for the parent

7Code line by line (only the new lines)

8Dry run: Example 2 again

1. h(5) → 1. h(4): left 0, right 1 → returns 2.
2. h(3): left 0, right 2 → gap 2 → −1.
3. h(2): left 0 (fine). Right = −1 → return −1 immediately (no abs check).
4. h(1): left = −1 → return −1 immediately. h(6) is never called, the right side is skipped.
5. Main: −1 != −1 is False → False ✓

Example 1 runs exactly as in Part B (no −1 ever appears) and returns True.

9Complexity & remember

• Time O(n): each node is visited at most once.
• Space: the call stack, as tall as the tree. In Example 1 the stack holds about one node per level, so for a nicely balanced tree it's about log n. But the input may be unbalanced (that's the whole question), and for a skewed tree the stack holds all n nodes. So the honest answer is O(n).
• Much faster than the BFS O(n²) on LeetCode.

Part D · Revision page

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

ex1 = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
ex2 = TreeNode(1, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))), TreeNode(6))
s = Solution()
print(s.isBalanced(ex1))     # True
print(s.isBalanced(ex2))     # False  (Part B's buggy code prints True here)
print(s.isBalanced(None))    # True
print(s.isBalanced(TreeNode(1, TreeNode(2, TreeNode(3)))))   # False

Based on this video: Balanced Binary Tree | BFS & DFS