Tree Depth and Balance

The Idea

Height is the longest chain of links from a node down to a leaf, and it decides what every tree operation costs. A tree is balanced when the two sides of each node differ in height by at most one. Balanced means height near log n; skewed means height n.

Real-World Example

A volunteer fire brigade's callout cascade, where each person rings two others. Kept balanced, the whole roster is awake within a handful of rounds. Let it collapse into one person ringing one person and the last volunteer hears about the fire far too late.

The Code

class Node:
    def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))

def is_balanced(n):
    if n is None: return True
    gap = abs(height(n.left) - height(n.right))    # sides may differ by 1 at most
    return gap <= 1 and is_balanced(n.left) and is_balanced(n.right)

full = Node(2, Node(1), Node(3))
skew = Node(1, None, Node(2, None, Node(3)))       # a chain wearing a tree costume
print(height(full), is_balanced(full))   # 2 True
print(height(skew), is_balanced(skew))   # 3 False

class Node:
  def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r

def height(n):
  return 0 if n is None else 1 + max(height(n.left), height(n.right))

t = Node(1, Node(2, Node(4)), Node(3))
print(height(t), height(t.right))