Vertical Order Traversal of Binary Tree in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the root node and its horizontal distance 0.

DSA Typescript

const queue: Array<[TreeNode, number]> = [];
queue.push([1]);

Drag options to blanks, or click blank then click option'

A[root, 0]

B[0, root]

C[root]

D[null, 0]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the order of root and distance.

Pushing only the root without distance.

We push a tuple with the root node and horizontal distance 0 to start the traversal.

2fill in blank

medium

Complete the code to update the map with the current node's value at its horizontal distance.

DSA Typescript

if (!map.has(hd)) {
  map.set(hd, []);
}
map.get(hd)!.[1](node.val);

Drag options to blanks, or click blank then click option'

Aunshift

Bpop

Cshift

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes the last element.

Using shift or unshift which affect the start of the array.

We use push to add the node's value to the array at the horizontal distance.

3fill in blank

hard

Fix the error in the code that adds the left child to the queue with updated horizontal distance.

DSA Typescript

if (node.left) {
  queue.[1]([node.left, hd - 1]);
}

Drag options to blanks, or click blank then click option'

Ashift

Bpop

Cpush

Dunshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop which removes elements.

Using shift or unshift which remove or add at the front.

We use push to add the left child at the end of the queue for BFS.

4fill in blank

hard

Fill both blanks to sort the keys and build the final vertical order array.

DSA Typescript

const sortedKeys = Array.from(map.keys()).[1]((a, b) => a [2] b);
const result: number[][] = [];
for (const key of sortedKeys) {
  result.push(map.get(key)!);
}

Drag options to blanks, or click blank then click option'

Asort

Breverse

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using reverse which reverses but does not sort.

Using + instead of - in comparator.

We sort keys in ascending order using sort with comparator (a, b) => a - b.

5fill in blank

hard

Fill all three blanks to complete the vertical order traversal function.

DSA Typescript

function verticalOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map<number, number[]>();
  const queue: Array<[TreeNode, number]> = [];
  queue.push([1]);
  while (queue.length > 0) {
    const [node, hd] = queue.shift()!;
    if (!map.has(hd)) {
      map.set(hd, []);
    }
    map.get(hd)!.[2](node.val);
    if (node.left) queue.push([node.left, hd [3] 1]);
    if (node.right) queue.push([node.right, hd + 1]);
  }
  const sortedKeys = Array.from(map.keys()).sort((a, b) => a - b);
  const result: number[][] = [];
  for (const key of sortedKeys) {
    result.push(map.get(key)!);
  }
  return result;
}

Drag options to blanks, or click blank then click option'

A[root, 0]

Bpush

C-

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push for map arrays.

Adding instead of subtracting for left child distance.

The queue starts with [root, 0]. We push node values to the map arrays. The left child's horizontal distance is hd - 1.

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