Balanced Binary Tree

The problem

A binary tree is made of nodes. Each node has a value, val, and two children, left and right; a missing child is null. You are given root, the top node, or null for an empty tree. The height of a tree is the number of nodes on its longest path from the top node down; an empty tree has height 0. A tree is balanced when, at every node, the tree that starts at the left child and the tree that starts at the right child differ in height by at most 1. Return true if the tree is balanced, otherwise false. An empty tree is balanced.

What to write

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function solve(root: TreeNode | null): boolean

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":null}

Output
true

Input
root = {"val":1,"left":{"val":2,"left":{"val":3,"left":null,"right":null},"right":null},"right":null}

Output
false

Constraints

0–500 acyclic tree nodes.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The rule must hold at every node, not only at the root, so the heights on both sides of every node have to be compared. An empty tree counts as balanced. A difference of exactly 1 is allowed; 2 or more is not.

2. Hint 2: Ask a smaller question

   Take example 2: node 1 has left child 2, and node 2 has left child 3. Write next to each node the height of the tree that starts there. At which node do the two sides differ by more than 1, and which numbers did you need to see that?

3. Hint 3: Name the pattern

   A node's height comes from its children's heights, and the rule at that node compares those same two heights. Children must answer before their parent: postorder tree recursion. A helper function that calls itself promises one thing: given any node, return the height of the tree that starts there, or -1 if that tree is not balanced. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   A height is never negative, so -1 can mean "not balanced". The helper returns -1 if either child returned -1 or if the two heights differ by more than 1. Otherwise it returns the true height: 1 plus the larger of the two.

5. Hint 5: Sketch the pseudocode

   Height of a node: if it is null, return 0. Get the left answer and the right answer with the same function. If either is -1, or they differ by more than 1, return -1. Otherwise return 1 plus the larger. The tree is balanced if the root's answer is not -1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Compute subtree heights bottom-up. Return a negative sentinel whenever a child is unbalanced or the two heights differ by more than one.

The slow way

At every node, measure the two heights the rule compares, each with a separate walk down, and compare them. It is correct, but every measurement walks part of the tree again. In a balanced tree, a node that has ten nodes above it on the way up to the root is walked ten times, once for each of them.

The insight

A parent needs two facts from each child: the child's height, and whether everything under the child is balanced. One walk from the bottom up can deliver both in a single number, because a real height is never negative: a helper function does the walk and returns -1 to say "not balanced" and the height otherwise. Children answer before parents, which is what postorder means.

Step by step

1. A helper returns the height of a subtree, 0 for an empty one. A subtree is a child together with everything below that child. Its height is the number of nodes on its longest way down, so an empty subtree has height 0. An empty subtree is balanced, and it ends the calls.
2. Ask the helper about the left and the right subtree. The helper calls itself, which is called recursion. It promises, for any node, the height of the subtree that starts there, or -1 if that subtree is not balanced. Both answers are needed to judge this node.
3. Answer -1 if a side is unbalanced or the heights are more than 1 apart. A tree is unbalanced if anything inside it is. A -1 from a child reports trouble further down, and two heights more than 1 apart are trouble at this node. Either way the parent must hear -1.
4. Otherwise answer the height: one more than the taller side. Both sides are balanced and close enough in height, so this subtree is balanced too. Its height is this node, which counts as 1, on top of the taller of its two sides.
5. The tree is balanced when the root's answer is not -1. The root's answer covers the whole tree. A -1 raised at any node is passed on by every node above that node, so the -1 always reaches the root.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. A helper returns the height of a subtree, 0 for an empty one
  function height(node) {
    if (!node) return 0;
    // 2. Ask the helper about the left and the right subtree
    const left = height(node.left);
    const right = height(node.right);
    // 3. Answer -1 if a side is unbalanced or the heights are more than 1 apart
    if (left < 0 || right < 0 || Math.abs(left - right) > 1) return -1;
    // 4. Otherwise answer the height: one more than the taller side
    return 1 + Math.max(left, right);
  }
  // 5. The tree is balanced when the root's answer is not -1
  return height(root) >= 0;
}

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function solve(root: TreeNode | null): boolean {
  // 1. A helper returns the height of a subtree, 0 for an empty one
  function height(node: TreeNode | null): number {
    if (!node) return 0;
    // 2. Ask the helper about the left and the right subtree
    const left = height(node.left);
    const right = height(node.right);
    // 3. Answer -1 if a side is unbalanced or the heights are more than 1 apart
    if (left < 0 || right < 0 || Math.abs(left - right) > 1) return -1;
    // 4. Otherwise answer the height: one more than the taller side
    return 1 + Math.max(left, right);
  }
  // 5. The tree is balanced when the root's answer is not -1
  return height(root) >= 0;
}

def solve(root):
    # 1. A helper returns the height of a subtree, 0 for an empty one
    def height(node):
        if node is None:
            return 0
        # 2. Ask the helper about the left and the right subtree
        left = height(node.left)
        right = height(node.right)
        # 3. Answer -1 if a side is unbalanced or the heights are more than 1 apart
        if left < 0 or right < 0 or abs(left - right) > 1:
            return -1
        # 4. Otherwise answer the height: one more than the taller side
        return 1 + max(left, right)

    # 5. The tree is balanced when the root's answer is not -1
    return height(root) >= 0

Example 2, traced

Input
root = {"val":1,"left":{"val":2,"left":{"val":3,"left":null,"right":null},"right":null},"right":null}

Output
false

Why it works

The helper is right for an empty subtree: height 0, balanced. For any node, if both children's answers are right, then the node's subtree is unbalanced exactly when a child said -1 or the two heights are more than 1 apart, and otherwise its height is 1 plus the larger. So the root's answer is right as well.

Time and space

Time O(n), extra space O(h). The helper runs once per node and once per missing child, with constant work each time: O(n) time in one walk. The unfinished calls form a chain from the root down, one per level: O(h) on the call stack for a tree of height h.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Check for -1 from a child before you compare heights. If -1 is treated as a height, a parent can find the two sides only 1 apart and report a normal height, and the trouble below is forgotten.
• A difference of exactly 1 is allowed. Testing for "1 or more" instead of "more than 1" rejects example 1, where the root has height 1 on its left and 0 on its right.
• Keep 0 as the height of an empty subtree. If a missing child returned -1, every node would see an unbalanced side below it, and every tree would be reported as not balanced.

Pattern

Postorder tree recursion. Builds on Maximum Depth of Binary Tree and Diameter of Binary Tree.

Keep going