Tree Depth and Balance
Trees & BST: lesson 7 of 14
Height decides speed, and balance decides height.
Lesson 7 of 14 · 5 min
Tree Depth and Balance
Step 1 of 7
Two trees, the same three values. One is a pyramid, one is a chain wearing a tree costume.
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 FalseYour turn
What does this print?
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))Mini quiz
1 / 3