Vertical Order Traversal
Trees & BST: lesson 13 of 14
Give every node an x-coordinate and read the tree in columns.
Lesson 13 of 14 · 6 min
Vertical Order Traversal
Step 1 of 9
columns4
column 0
3
Hang the tree on a grid. The root takes column 0; every step left is one less, every step right one more.
The Idea
Hang the tree on a grid. The root sits at column 0, a left child at one column less, a right child at one more. Nodes sharing a column line up vertically even when they sit in different branches.
Walk breadth-first, bucket each value by its column, then read the buckets left to right.
Real-World Example
A tournament bracket printed on a wall. Two matches from opposite halves of the draw can still line up in the same vertical strip of paper, and that strip is what you want to read as a unit.
The Code
from collections import defaultdict, deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def vertical(root):
cols, q = defaultdict(list), deque([(root, 0)]) # the root owns column 0
while q:
n, c = q.popleft() # BFS fills each column top-down
cols[c].append(n.val)
if n.left: q.append((n.left, c - 1)) # left is one column out
if n.right: q.append((n.right, c + 1))
return [cols[c] for c in sorted(cols)]
print(vertical(Node(3, Node(9), Node(20, Node(15), Node(7))))) # [[9], [3, 15], [20], [7]]Your turn
Fill in the blank.
from collections import defaultdict, deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
root = Node(3, Node(9), Node(20, Node(15), Node(7)))
cols, q = defaultdict(list), deque([(root, 0)])
while q:
n, c = q.popleft()
cols[c].append(n.val)
if n.left: q.append((n.left, ___))
if n.right: q.append((n.right, c + 1))
print([cols[c] for c in sorted(cols)]) # should print [[9], [3, 15], [20], [7]]Mini quiz
1 / 3