Balanced Binary Tree

Problem

A binary tree is balanced iff for every node, the depths of its two children differ by at most 1. Return true iff the given tree is balanced.

Constraints

• 0 ≤ nodes ≤ 5000

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def isBalanced(self, root):
        def height(node):
            if not node:
                return 0
            l = height(node.left)
            if l == -1:
                return -1
            r = height(node.right)
            if r == -1 or abs(l - r) > 1:
                return -1
            return 1 + max(l, r)
        return height(root) != -1

Java

class Solution {
    public boolean isBalanced(TreeNode root) { return depth(root) != -1; }
    private int depth(TreeNode n) {
        if (n == null) return 0;
        int l = depth(n.left);  if (l == -1) return -1;
        int r = depth(n.right); if (r == -1) return -1;
        if (Math.abs(l - r) > 1) return -1;
        return 1 + Math.max(l, r);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.