DSA Tracker

Visualize

Balanced Binary Tree

Bottom-up height with a -1 sentinel

time O(n)space O(h)

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.

Details

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].

Problem:Balanced Binary TreeEasy

Bottom-up height with a -1 sentinel

step 1 / 11

4
3
4
2
3
1
2

Call stack

height(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

Every step in words

Show all 11 steps
  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.
  2. Call height(2) on the left 2. Its own height depends on both children, so nothing can be decided here yet — recurse down first and let the answers climb back up.
  3. Call height(3) on the left 3. Its own height depends on both children, so nothing can be decided here yet — recurse down first and let the answers climb back up.
  4. the left 4 is a leaf: both null children return 0, |0 - 0| = 0 is fine, so it returns 1 + MAX(0, 0) = 1.
  5. the right 4 is a leaf: both null children return 0, |0 - 0| = 0 is fine, so it returns 1 + MAX(0, 0) = 1.
  6. At the left 3: left height 1, right height 1. |1 - 1| = 0 <= 1, so this subtree is balanced and reports height 1 + MAX(1, 1) = 2.
  7. the right 3 is a leaf: both null children return 0, |0 - 0| = 0 is fine, so it returns 1 + MAX(0, 0) = 1.
  8. At the left 2: left height 2, right height 1. |2 - 1| = 1 <= 1, so this subtree is balanced and reports height 1 + MAX(2, 1) = 3.
  9. the right 2 is a leaf: both null children return 0, |0 - 0| = 0 is fine, so it returns 1 + MAX(0, 0) = 1.
  10. At 1: left height 3, right height 1. |3 - 1| = 2 > 1, so this node is the one that breaks the rule — return the -1 sentinel instead of a height.
  11. height(1) returned -1, so isBalanced = false. Every node was visited once and returned once — O(n) — and the badge on each node is the height it reported (or -1 where the rule broke).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Balanced Binary Tree in the editorAll Binary Trees problemsBack to roadmap