Vertical Order Traversal of Binary Tree in DSA Javascript - 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 horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

Repeat until queue empty

↓

Sort map keys

↓

Output values grouped by sorted keys

↓

Done

Traverse the tree level by level, track horizontal distances, group nodes by these distances, then output groups from left to right.

Execution Sample

DSA Javascript

function verticalOrder(root) {
  const map = new Map();
  const queue = [[root, 0]];
  while(queue.length) {
    const [node, hd] = queue.shift();
    if(!map.has(hd)) map.set(hd, []);
    map.get(hd).push(node.val);
    if(node.left) queue.push([node.left, hd - 1]);
    if(node.right) queue.push([node.right, hd + 1]);
  }
  return [...map.keys()].sort((a,b) => a-b).map(k => map.get(k));
}

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

Execution Table

Step	Operation	Node Visited (val)	Horizontal Distance (hd)	Map State (hd: [values])	Queue State	Visual State
1	Start with root	1	0	0: [1]	[[2, -1], [3, 1]]	Root node 1 at hd=0
2	Visit node	2	-1	-1: [2], 0: [1]	[[3, 1], [4, -2], [5, 0]]	Left child 2 at hd=-1
3	Visit node	3	1	-1: [2], 0: [1], 1: [3]	[[4, -2], [5, 0], [6, 0], [7, 2]]	Right child 3 at hd=1
4	Visit node	4	-2	-2: [4], -1: [2], 0: [1], 1: [3]	[[5, 0], [6, 0], [7, 2]]	Left child 4 at hd=-2
5	Visit node	5	0	-2: [4], -1: [2], 0: [1,5], 1: [3]	[[6, 0], [7, 2]]	Node 5 at hd=0
6	Visit node	6	0	-2: [4], -1: [2], 0: [1,5,6], 1: [3]	[[7, 2]]	Node 6 at hd=0
7	Visit node	7	2	-2: [4], -1: [2], 0: [1,5,6], 1: [3], 2: [7]	[]	Right child 7 at hd=2
8	Queue empty	N/A	N/A	-2: [4], -1: [2], 0: [1,5,6], 1: [3], 2: [7]	[]	Traversal complete

💡 Queue is empty, all nodes visited.

Variable Tracker

Variable	Start	After Step 1	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,0],[7,2]]	[[5,0],[6,0],[7,2]]	[[6,0],[7,2]]	[[7,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,6], -1:[2], 1:[3], -2:[4]}	{0:[1,5,6], -1:[2], 1:[3], -2:[4], 2:[7]}	{0:[1,5,6], -1:[2], 1:[3], -2:[4], 2:[7]}

Key Moments - 3 Insights

Why do we use a queue with nodes paired with horizontal distances?

The queue helps us visit nodes level by level (BFS). Pairing nodes with horizontal distances lets us group nodes vertically. See execution_table steps 1-7 where queue holds nodes with their hd.

Why do we add left child with hd-1 and right child with hd+1?

Left child is one step left, so hd decreases by 1; right child is one step right, so hd increases by 1. This is shown in execution_table steps 2-7 where hd changes accordingly.

How do we know when traversal is complete?

When the queue is empty, all nodes have been visited. Execution_table step 8 shows queue empty and traversal done.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the map state?

A -2: [4], -1: [2], 0: [1,5], 1: [3]

B 0: [1,5], 1: [3], 2: [7]

C -1: [2], 0: [1], 1: [3]

D -2: [4], 0: [1,5,6], 1: [3]

💡 Hint

Check the 'Map State' column in execution_table row for Step 5.

At which step does the queue become empty?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Queue State' column in execution_table; empty queue is shown at Step 8.

If we swapped left and right child enqueue order, how would the map values at hd=0 change?

A They would appear in reverse order [1,6,5]

B They would remain [1,5,6]

C Only the first value would change

D Map keys would change

💡 Hint

Check variable_tracker for map values at hd=0 after steps 5 and 6.

Concept Snapshot

Vertical Order Traversal:
- Use BFS with queue storing (node, horizontal distance)
- Left child hd = parent hd - 1
- Right child hd = parent hd + 1
- Group nodes by hd in map
- Sort keys and output grouped nodes
- Result shows nodes vertically from left to right

Full Transcript

Vertical Order Traversal visits nodes level by level, tracking their horizontal distance from the root. We use a queue to hold nodes paired with their horizontal distance. Starting at root with hd=0, we add nodes to a map grouped by hd. Left children get hd-1, right children hd+1. After visiting all nodes, we sort the map keys and output the grouped nodes. This shows the tree nodes vertically from left to right.