Balanced Binary Tree – Solution & Complexity

Q: What is the time and space complexity of Balanced Binary Tree?

The optimal Balanced Binary Tree solution runs in `O(n)` time and `O(h)` space. Run one postorder DFS that returns subtree height or an imbalance sentinel as soon as a node fails.

Q: What is the most efficient way to solve Balanced Binary Tree?

Run one postorder DFS that returns subtree height or an imbalance sentinel as soon as a node fails. This gives `O(n)` time complexity, and is a classic binary tree, depth first search, and recursion problem.

Q: How do you solve Balanced Binary Tree in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked Balanced Binary Tree solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Balanced Binary Tree an easy or hard interview question?

Balanced Binary Tree is generally rated **Easy**. It tests binary tree, depth first search, and recursion, which are common coding-interview patterns.

Solution Walkthrough

1. Understand the balance condition

Balance is a local rule that must hold at every node, not just at the root.
That means we need subtree heights, but we also need to know whether a deeper subtree has already failed.

2. Brute-force by recomputing heights

For each node, compute the height of the left subtree and the right subtree, compare them, then recurse into both children.
This is correct, but repeated height work can make it O(n^2) on skewed trees.

def is_balanced(root: TreeNode) -> bool:
    def height(node: TreeNode | None) -> int:
        if node is None:
            return 0
        return 1 + max(height(node.left), height(node.right))

    if root is None:
        return True

    return (
        abs(height(root.left) - height(root.right)) <= 1
        and is_balanced(root.left)
        and is_balanced(root.right)
    )

3. Return a sentinel when a subtree is already unbalanced

A postorder traversal naturally computes child heights before the parent.
If either child is already unbalanced, bubble up a sentinel like -1 immediately instead of continuing normal height math.

4. Combine height and balance in one DFS

Return the subtree height when everything below the node is balanced.
Return -1 as soon as a node fails the balance check.
The tree is balanced exactly when the root does not return -1.

def is_balanced(root: TreeNode) -> bool:
    def dfs(node: TreeNode | None) -> int:
        if node is None:
            return 0

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

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

        if abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)

    return dfs(root) != -1

5. Dry run / postorder trace

Trace root = [1,2,2,3,3,null,null,4,4].

node	left height	right height	return value
leaf `4`	0	0	1
leaf `4`	0	0	1
node `3` (left subtree)	1	1	2
node `3` (right child of left subtree)	0	0	1
node `2` (left child of root)	2	1	3
node `2` (right child of root)	0	0	1
root `1`	3	1	`-1` (unbalanced)

6. Common mistakes and follow-ups

Computing height separately at every node, which degrades to O(n^2).
Treating an empty tree as unbalanced when it should return true.
Forgetting that a subtree already marked unbalanced should short-circuit immediately.
Follow-up: how would you implement the same idea iteratively with an explicit postorder stack?

7. Edge cases to test mentally

[] and [1] are both balanced.
A chain of three nodes is unbalanced at the root.
Perfect trees are balanced at every level.
A tree can look balanced at the root but still fail deeper down, so every subtree must be checked.

8. Final full solution and complexity

A single postorder DFS returns each subtree height once and uses -1 as an imbalance sentinel. Time is O(n), and extra stack space is O(h) where h is the tree height.

def is_balanced(root: TreeNode) -> bool:
    def dfs(node: TreeNode | None) -> int:
        if node is None:
            return 0

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

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

        if abs(left_height - right_height) > 1:
            return -1
        return 1 + max(left_height, right_height)

    return dfs(root) != -1

Balanced Binary Tree – Solution & Complexity

Solution Walkthrough

1. Understand the balance condition

2. Brute-force by recomputing heights

3. Return a sentinel when a subtree is already unbalanced

4. Combine height and balance in one DFS

5. Dry run / postorder trace

6. Common mistakes and follow-ups

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of Balanced Binary Tree?

What is the most efficient way to solve Balanced Binary Tree?

How do you solve Balanced Binary Tree in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is Balanced Binary Tree an easy or hard interview question?

See also