Framework Thinking - Neetcode 150 - Balanced Binary Tree

Here is solutions for Balanced Binary Tree.

1. Understand the problem

You are given the root of a binary tree.

A tree is height-balanced if:

For every node,

|height(left subtree) - height(right subtree)| <= 1

Your goal:

Return True if the binary tree is height-balanced, otherwise False

2. Clarify constraints, asks 4 - 5 questions including edge cases.

What is the size limit of the tree?

Can up to 10^4 nodes.
Must avoid O(N^2) solutions; recursion depth must be safe.

What should the function return for an empty tree?

Balanced → Return True.

Are there negative or duplicate values?

Values don’t matter. Only structure matters.

Is the tree guaranteed to be valid?

Yes, nodes follow TreeNode definition.

What about skewed trees (like a linked list)?

These are common edge cases; height could be large.

3. Explore examples.

Example 1:

=> Balanced → return True

Example 2

=> Heights differ by > 1 → return False

Example 3

root = None

=> Return True

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Naive (Height repeated calculation) — Time O(N^2), Space O(H), worst case O(N)

For every node:

- compute left height

- compute right height

- check balance

Recursively do this for all nodes.

Time: O(N^2).
Space: O(H), worst case O(N)

4.2. Solution 2 — Optimized DFS with Early Stop (Post-order) — Time O(N), Space O(H), worst case O(N)

Key Idea

Use DFS:

At each node return:

height of subtree
OR -1 if subtree is unbalanced

=> If any subtree returns -1, propagate -1 upward immediately.

If left subtree height = -1 → unbalanced
If right subtree height = -1 → unbalanced
If abs(left - right) > 1 → unbalanced → return -1
Else return 1 + max(left, right)

Time: O(N).
Space: O(H), worst case O(N)

5. Implement solutions.

5.1. Naive Solution - Time O(N^2), Space O(H), worst case O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        left = self.height(root.left)
        right = self.height(root.right)
        if abs(left - right) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def height(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.height(root.left), self.height(root.right))

Time: O(N^2)
Space: O(N)

5.2. DFS Recursion Solution - By Idea return height or -1 - Time O(N), Space O(H), worst case O(N)

At each node return:

height of subtree
OR -1 if subtree is unbalanced

class Solution:
    def isBalanced(self, root):

        def dfs(node):
            if not node:
                return 0  # height of empty tree

            left = dfs(node.left)
            if left == -1:
                return -1

            right = dfs(node.right)
            if right == -1:
                return -1

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

            return 1 + max(left, right)

        return dfs(root) != -1

Time: O(N)
Space: O(N)

5.3. DFS Recursion Solution - Track the status of root node - Return [isBalanced, height] - Time O(N), Space O(H), worst case O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return [True, 0]

            left, right = dfs(root.left), dfs(root.right)
            balanced = left[0] and right[0] and abs(left[1] - right[1]) <= 1
            return [balanced, 1 + max(left[1], right[1])]

        return dfs(root)[0]

Time: O(N)
Space: O(N)

5.4. Iterative DFS - Time O(N), Space O(N)

class Solution:
    def isBalanced(self, root):
        if not root:
            return True

        stack = [(root, False)]
        height = {None: 0}

        while stack:
            node, visited = stack.pop()

            if not node:
                continue

            if not visited:
                # Postorder: push node again after children
                stack.append((node, True))
                stack.append((node.left, False))
                stack.append((node.right, False))

            else:
                # Both children have been processed → compute heights
                left_h = height.get(node.left)
                right_h = height.get(node.right)

                # If a child is already unbalanced
                if left_h == -1 or right_h == -1:
                    height[node] = -1
                    continue

                # Check balance condition
                if abs(left_h - right_h) > 1:
                    height[node] = -1
                else:
                    height[node] = 1 + max(left_h, right_h)

        return height[root] != -1

Idea: Just a way to call the right height.

Time: O(N)
Space: O(N)

6. Dry run testcases.

=> Store each value for each steps.

December 2, 2025