Tree Balance Check

An interactive, step-by-step visualisation of Tree Balance Check.

Category: Trees
Time complexity: O(n)
Space complexity: O(h)

Pseudocode

check(t) returns height, sets balanced=False if |lh−rh|>1 anywhere

Reference implementation

balanced = True
def check(t):
    nonlocal balanced
    if not t: return -1
    lh, rh = check(t.l), check(t.r)
    if abs(lh - rh) &gt; 1: balanced = False
    return 1 + max(lh, rh)

Open the interactive Tree Balance Check visualisation →