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

Concept Flow - Vertical Order Traversal of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Traverse left child: hd = hd - 1

↓

Traverse right child: hd = hd + 1

↓

Store nodes in map by hd

↓

Sort map keys from min to max hd

↓

Output nodes grouped by hd in order

Start from root with horizontal distance 0, traverse left and right children adjusting horizontal distance, store nodes by distance, then output nodes grouped by these distances from left to right.

Execution Sample

DSA Typescript

function verticalOrder(root) {
  if (!root) return [];
  let map = new Map();
  let queue = [[root, 0]];
  while(queue.length) {
    let [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 traverses the tree level by level, tracks horizontal distances, groups nodes by these distances, and returns the vertical order traversal.

Execution Table

Step	Operation	Node Visited	Horizontal Distance (hd)	Map State (hd -> nodes)	Queue State	Visual Tree State
1	Start with root	1	0	{0: [1]}	[[2, -1], [3, 1]]	1 / \ 2 3
2	Visit left child	2	-1	{0: [1], -1: [2]}	[[3, 1], [4, -2], [5, 0]]	1 / \ 2 3 / \ 4 5
3	Visit right child	3	1	{0: [1], -1: [2], 1: [3]}	[[4, -2], [5, 0], [6, 0], [7, 2]]	1 / \ 2 3 / \ / \ 4 5 6 7
4	Visit left child of 2	4	-2	{0: [1], -1: [2], 1: [3], -2: [4]}	[[5, 0], [6, 0], [7, 2]]	1 / \ 2 3 / \ / \ 4 5 6 7
5	Visit right child of 2	5	0	{0: [1, 5], -1: [2], 1: [3], -2: [4]}	[[6, 0], [7, 2]]	1 / \ 2 3 / \ / \ 4 5 6 7
6	Visit left child of 3	6	0	{0: [1, 5, 6], -1: [2], 1: [3], -2: [4]}	[[7, 2]]	1 / \ 2 3 / \ / \ 4 5 6 7
7	Visit right child of 3	7	2	{0: [1, 5, 6], -1: [2], 1: [3], -2: [4], 2: [7]}	[]	1 / \ 2 3 / \ / \ 4 5 6 7
8	Queue empty, end traversal	N/A	N/A	{-2: [4], -1: [2], 0: [1, 5, 6], 1: [3], 2: [7]}	[]	1 / \ 2 3 / \ / \ 4 5 6 7

💡 Queue is empty, all nodes visited and grouped by horizontal distance.

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

Key Moments - 3 Insights

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

Starting at 0 for the root (see Step 1 in execution_table) gives a reference point. Left children decrease hd by 1, right children increase hd by 1, allowing grouping nodes vertically.

Why do nodes with the same horizontal distance appear in the order they are visited?

Because we use a queue for level order traversal (see queue state in execution_table), nodes at the same hd are visited top-down, left to right, preserving vertical order.

What happens if the tree is empty?

If root is null, the queue starts empty and traversal ends immediately with an empty map, so output is empty (not shown in table but implied).

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what nodes are stored at horizontal distance 0 in the map?

A [1, 5, 6]

B [1, 5]

C [1]

D [5]

💡 Hint

Check the 'Map State' column at Step 5 in execution_table.

At which step does the horizontal distance 2 first get a node added?

A Step 7

B Step 5

C Step 4

D Step 6

💡 Hint

Look at the 'Map State' column for hd=2 in execution_table rows.

If we changed the traversal to depth-first instead of breadth-first, how would the queue state change?

A Queue would hold nodes level by level as shown

B Queue would be empty from the start

C Queue would hold nodes deeper in one branch before visiting siblings

D Queue would hold nodes in random order

💡 Hint

Compare queue behavior in breadth-first (execution_table) vs depth-first traversal.

Concept Snapshot

Vertical Order Traversal of Binary Tree:
- Assign horizontal distance (hd) 0 to root
- Left child hd = parent hd - 1
- Right child hd = parent hd + 1
- Use queue for level order traversal
- Group nodes by hd in a map
- Output nodes sorted by hd from left to right

Full Transcript

Vertical order traversal visits nodes of a binary tree grouped by their horizontal distance from the root. We start at the root with horizontal distance zero. For each node, the left child is assigned hd minus one, and the right child hd plus one. We use a queue to traverse the tree level by level, storing nodes in a map keyed by their hd. After visiting all nodes, we sort the keys of the map and output the nodes grouped by these keys. This approach ensures nodes are output vertically from left to right, and top to bottom within each vertical line.