{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Balanced Binary Tree – Solution & Complexity

Interview solutions
/
Balanced Binary Tree

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 5: Dry run / postorder trace

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

    nodeleft heightright heightreturn value
    leaf 4001
    leaf 4001
    node 3 (left subtree)112
    node 3 (right child of left subtree)001
    node 2 (left child of root)213
    node 2 (right child of root)001
    root 131-1 (unbalanced)

  6. Step 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. Step 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. Step 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

FAQ

See also

Practice Balanced Binary Tree online (run code in the browser)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)Diameter of Binary Tree solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?