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.

Practice

1. What does Vertical Order Traversal of a binary tree mean?

easy

A. Nodes are grouped by their vertical columns from left to right

B. Nodes are visited level by level from top to bottom

C. Nodes are visited in preorder (root, left, right)

D. Nodes are visited in inorder (left, root, right)

Solution

1. Step 1: Understand vertical columns in a tree

   Vertical order groups nodes by their horizontal distance from the root, called columns.

2. Step 2: Define vertical order traversal

   Nodes in the same vertical column are collected and output from leftmost to rightmost column.

3. Final Answer:

   Nodes are grouped by their vertical columns from left to right -> Option A

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns from left to right, not levels or preorder [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Ignoring horizontal distance concept

2. Which TypeScript data structure is best to store nodes by their vertical column during vertical order traversal?

easy

A. Map

B. Set<number>

C. Array<number>

D. string[]

Solution

1. Step 1: Identify need to map columns to nodes

   We need to store nodes grouped by their column index, so a mapping from column number to list of nodes is required.

2. Step 2: Choose appropriate TypeScript structure

   A Map with keys as column numbers and values as arrays of node values fits perfectly.

3. Final Answer:

   Map<number, number[]> -> Option A

4. Quick Check:

   Map column to node list = Map<number, number[]> [OK]

Hint: Use Map to link column numbers to node arrays [OK]

Common Mistakes:

• Using Set which does not store duplicates or order
• Using plain arrays without column keys
• Using string arrays which don't map columns

3. Given this TypeScript code for vertical order traversal, what is the output?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map();
  const queue: [TreeNode, number][] = [[root, 0]];
  while (queue.length) {
    const [node, col] = queue.shift()!;
    if (!map.has(col)) map.set(col, []);
    map.get(col)!.push(node.val);
    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }
  return Array.from(map.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

console.log(verticalOrder(root));

medium

A. [[7], [3], [1, 5, 6], [2], [4]]

B. [[4], [2], [1, 5, 6], [3], [7]]

C. [[1], [2, 3], [4, 5, 6, 7]]

D. [[4], [2, 5], [1, 6], [3, 7]]

Solution

1. Step 1: Assign columns to nodes during BFS

   Root (1) at col 0; left child (2) at -1; right child (3) at +1; and so on. Nodes grouped by columns: - -2: 4 - -1: 2 - 0: 1, 5, 6 - 1: 3 - 2: 7

2. Step 2: Sort columns and output node lists

   Sorted columns from left to right: -2, -1, 0, 1, 2. Output arrays accordingly.

3. Final Answer:

   [[4], [2], [1, 5, 6], [3], [7]] -> Option B

4. Quick Check:

   Column grouping matches output D [OK]

Hint: Track column indices during BFS, then sort keys [OK]

Common Mistakes:

• Mixing up column indices for left/right children
• Not sorting columns before output
• Using DFS instead of BFS causing wrong order

4. The following TypeScript code for vertical order traversal has a bug. What is the bug?

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map();
  const queue: [TreeNode, number][] = [[root, 0]];
  while (queue.length) {
    const [node, col] = queue.pop()!;
    if (!map.has(col)) map.set(col, []);
    map.get(col)!.push(node.val);
    if (node.left) queue.push([node.left, col - 1]);
    if (node.right) queue.push([node.right, col + 1]);
  }
  return Array.from(map.entries())
    .sort((a, b) => a[0] - b[0])
    .map(entry => entry[1]);
}

medium

A. map.get(col) returns undefined

B. Missing check for null root

C. Using queue.pop() causes DFS instead of BFS traversal

D. Sorting map entries is incorrect

Solution

1. Step 1: Identify queue operation used

   The code uses queue.pop(), which removes the last element, making it a stack (DFS) behavior.

2. Step 2: Explain impact on vertical order traversal

   Vertical order requires BFS (level order) to maintain correct node order per column. Using pop() breaks this order.

3. Final Answer:

   Using queue.pop() causes DFS instead of BFS traversal -> Option C

4. Quick Check:

   pop() = DFS, need shift() for BFS [OK]

Hint: Use shift() for BFS queue, not pop() [OK]

Common Mistakes:

• Confusing pop() with shift() in queue
• Ignoring traversal order effect on output
• Assuming map.get always returns array without check

5. You want to modify vertical order traversal to sort nodes within the same column by their row (depth) and then by value ascending. Which approach is best?

hard

A. Traverse tree using DFS only and collect nodes in order

B. Use a Set per column to avoid duplicates

C. Sort nodes globally after traversal ignoring columns

D. Store nodes as tuples (row, value) per column and sort before output

Solution

1. Step 1: Understand sorting requirement within columns

   Nodes in the same column must be sorted first by their row (depth), then by value ascending.

2. Step 2: Choose data structure to store row and value

   Store tuples (row, value) for each node in the column map, then sort these tuples before output.

3. Step 3: Explain why other options fail

   Set ignores duplicates and order; DFS alone doesn't guarantee order; global sort ignores column grouping.

4. Final Answer:

   Store nodes as tuples (row, value) per column and sort before output -> Option D

5. Quick Check:

   Sort by row and value per column = store tuples and sort [OK]

Hint: Keep (row, value) pairs per column, then sort [OK]

Common Mistakes:

• Using Set which loses order and duplicates
• Relying on DFS without tracking rows
• Sorting all nodes ignoring column grouping