Pattern visualizer

Balanced Binary Tree

Checking balance top-down recomputes depths over and over. Instead, compute height bottom-up and let each node check itself on the way back: if a child returns -1, or the two child heights differ by more than 1, return -1 right away. The root sees -1 exactly when some node broke the rule. Animated on: Given the root of a binary tree, decide whether it is height-balanced: at every node, the left and right subtree heights differ by at most 1. Tree: [1, 2, 2, 3, 3, null, null, 4, 4]..

Bottom-up height with a -1 sentinel

time O(n)space O(h)step 1 / 11

Call stack

height(1)

line 1

Call height(1). Its own height depends on both children, so nothing can be decided here yet — recurse down first and let the answers climb back up.

Pseudocode

1FUNCTION height(node):
2  IF node = null:  RETURN 0
3  l <- height(node.left)
4  IF l = -1:  RETURN -1
5  r <- height(node.right)
6  IF r = -1:  RETURN -1
7  IF |l - r| > 1:  RETURN -1
8  RETURN 1 + MAX(l, r)
9 
10RETURN height(root) != -1

← / → step · space play · Home restart

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap