Balanced Binary Tree

easy tree dfs

Problem

Given a binary tree, decide if it is height-balanced — a tree in which the depth of the two subtrees of every node never differs by more than one.

Inputroot = [3,9,20,null,null,15,7]

Outputtrue

Every node has subtrees whose heights differ by at most 1.

tree (level-order, "null" for empty)

def is_balanced(root):
    def height(node):
        if not node: return 0
        lh = height(node.left)
        if lh == -1: return -1
        rh = height(node.right)
        if rh == -1 or abs(lh - rh) > 1: return -1
        return 1 + max(lh, rh)
    return height(root) != -1

function isBalanced(root) {
  function height(node) {
    if (!node) return 0;
    const lh = height(node.left);
    if (lh === -1) return -1;
    const rh = height(node.right);
    if (rh === -1 || Math.abs(lh - rh) > 1) return -1;
    return 1 + Math.max(lh, rh);
  }
  return height(root) !== -1;
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }
    int height(TreeNode n) {
        if (n == null) return 0;
        int lh = height(n.left);
        if (lh == -1) return -1;
        int rh = height(n.right);
        if (rh == -1 || Math.abs(lh - rh) > 1) return -1;
        return 1 + Math.max(lh, rh);
    }
}

class Solution {
public:
    bool isBalanced(TreeNode* root) { return height(root) != -1; }
    int height(TreeNode* n) {
        if (!n) return 0;
        int lh = height(n->left);
        if (lh == -1) return -1;
        int rh = height(n->right);
        if (rh == -1 || abs(lh - rh) > 1) return -1;
        return 1 + max(lh, rh);
    }
};

Explanation

A tree is balanced when, at every node, the left and right subtree heights differ by at most one. The neat trick here is to compute heights bottom-up and use a single special value, -1, to mean "already unbalanced".

The helper height(node) returns the real height of a subtree, but if it ever discovers an imbalance, it returns -1 instead.

So at each node we get lh = height(left) and rh = height(right). If either came back -1, or if |lh - rh| > 1, this node is unbalanced too, so we return -1. Otherwise the height is 1 + max(lh, rh).

Because -1 propagates straight back up the recursion, the moment any subtree is unbalanced the whole call chain short-circuits — no extra passes needed.

At the end, is_balanced is simply "did the root return something other than -1?". For [3,9,20,null,null,15,7] every subtree's heights differ by at most 1, so it returns true.

Time: O(n) Space: O(h) recursion