Vertical Order Traversal of Binary Tree in DSA Go - Execution Trace

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for BFS traversal

↓

Dequeue node

↓

Add node value to map at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort keys of map

↓

Output values in order of sorted keys

Traverse the tree level by level, track horizontal distance (hd) for each node, group nodes by hd, then output groups sorted by hd.

Execution Sample

DSA Go

type Node struct {
  Val int
  Left, Right *Node
}

func VerticalOrder(root *Node) [][]int {
  // BFS with hd tracking
}

This code performs vertical order traversal by BFS, grouping nodes by horizontal distance.

Execution Table

Step	Operation	Node Processed (Val, hd)	Map State (hd: [values])	Queue State (Val, hd)	Visual State
1	Start BFS	Root (1, 0)	{}	[(1,0)]	Tree: 1 / \ 2 3 / \ \ 4 5 6
2	Dequeue node	(1,0)	{0: [1]}	[(2,-1),(3,1)]	Added 1 at hd=0
3	Dequeue node	(2,-1)	{0: [1], -1: [2]}	[(3,1),(4,-2),(5,0)]	Added 2 at hd=-1
4	Dequeue node	(3,1)	{0: [1], -1: [2], 1: [3]}	[(4,-2),(5,0),(6,2)]	Added 3 at hd=1
5	Dequeue node	(4,-2)	{0: [1], -1: [2], 1: [3], -2: [4]}	[(5,0),(6,2)]	Added 4 at hd=-2
6	Dequeue node	(5,0)	{0: [1,5], -1: [2], 1: [3], -2: [4]}	[(6,2)]	Added 5 at hd=0
7	Dequeue node	(6,2)	{0: [1,5], -1: [2], 1: [3], -2: [4], 2: [6]}	[]	Added 6 at hd=2
8	Queue empty	None	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}	[]	Traversal complete
9	Sort keys and output	None	Output order: [4], [2], [1,5], [3], [6]	[]	Final vertical order

💡 Queue is empty, all nodes processed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Queue	[(1,0)]	[(2,-1),(3,1)]	[(3,1),(4,-2),(5,0)]	[(4,-2),(5,0),(6,2)]	[(5,0),(6,2)]	[(6,2)]	[]	[]
Map	{}	{0: [1]}	{0: [1], -1: [2]}	{0: [1], -1: [2], 1: [3]}	{0: [1], -1: [2], 1: [3], -2: [4]}	{0: [1,5], -1: [2], 1: [3], -2: [4]}	{0: [1,5], -1: [2], 1: [3], -2: [4], 2: [6]}	{-2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]}

Key Moments - 3 Insights

Why do we assign horizontal distance (hd) starting from 0 at root?

Assigning hd=0 at root gives a reference point. Left child gets hd-1, right child hd+1, so nodes align vertically by hd. See execution_table rows 2-7 where hd changes.

Why do we use a queue for traversal instead of recursion?

Queue ensures level order (BFS) traversal, so nodes are processed top to bottom per vertical line. This keeps vertical order correct. See execution_table queue states from step 2 to 7.

How do we get the final vertical order after traversal?

After BFS, map keys (hd) are sorted from smallest to largest. Values at each hd form one vertical line. See execution_table step 9 for sorted output.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the queue state?

A [(5,0),(6,2)]

B [(4,-2),(5,0),(6,2)]

C [(3,1),(4,-2),(5,0)]

D [(2,-1),(3,1)]

💡 Hint

Check the 'Queue State' column at step 4 in execution_table

At which step does the map first contain the key hd=1?

A Step 5

B Step 3

C Step 4

D Step 6

💡 Hint

Look at 'Map State' column in execution_table rows 3 and 4

If the root had no left child, how would the map change after step 3?

A No entry for hd=-1

B No entry for hd=1

C No entry for hd=0

D Map would be empty

💡 Hint

Left child nodes have hd = parent hd - 1; see variable_tracker and execution_table

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Assign horizontal distance (hd) 0 to root
- Use BFS with queue to traverse nodes
- For each node, add value to map[hd]
- Left child hd = hd - 1, right child hd = hd + 1
- After traversal, sort map keys
- Output node values grouped by sorted hd

Full Transcript

Vertical Order Traversal visits nodes of a binary tree grouped by their vertical lines. We start at the root with horizontal distance zero. Using a queue, we do a breadth-first search. Each node's value is added to a map keyed by its horizontal distance. Left children get hd one less than parent, right children one more. After processing all nodes, we sort the keys of the map and output the values in that order. This way, nodes are grouped vertically from left to right, and top to bottom within each vertical line.