Vertical Order Traversal of Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Vertical Order Traversal for a Simple Tree

What is the vertical order traversal output of the following binary tree?

Tree structure:
1
/ \
2 3
/ \
4 5

DSA Typescript

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

function verticalOrderTraversal(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map<number, number[]>();
  const queue: Array<[TreeNode, number]> = [[root, 0]];
  let min = 0, max = 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]);
    min = Math.min(min, col);
    max = Math.max(max, col);
  }

  const result: number[][] = [];
  for (let i = min; i <= max; i++) {
    result.push(map.get(i)!);
  }
  return result;
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
console.log(verticalOrderTraversal(root));

A [[2],[4,1],[3],[5]]

B [[2],[1],[4,3],[5]]

C [[2],[1,4],[3],[5]]

D [[1],[2,3],[4,5]]

💡 Hint

Think about columns from left to right and nodes in each column by level order.

The vertical order traversal groups nodes by their horizontal distance from root. Here, 2 is at column -1, 1 and 4 at 0, 3 at 1, and 5 at 2.

❓ Predict Output

intermediate

Vertical Order Traversal Output with Multiple Nodes in Same Column and Row

What is the vertical order traversal output of this binary tree?

Tree structure:
3
/ \
9 8
/ \ / \
4 0 1 7

DSA Typescript

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

function verticalOrderTraversal(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map<number, number[]>();
  const queue: Array<[TreeNode, number]> = [[root, 0]];
  let min = 0, max = 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]);
    min = Math.min(min, col);
    max = Math.max(max, col);
  }

  const result: number[][] = [];
  for (let i = min; i <= max; i++) {
    result.push(map.get(i)!);
  }
  return result;
}

const root = new TreeNode(3, new TreeNode(9, new TreeNode(4), new TreeNode(0)), new TreeNode(8, new TreeNode(1), new TreeNode(7)));
console.log(verticalOrderTraversal(root));

A [[4],[9,0],[3,1],[8],[7]]

B [[4],[9],[3,0,1],[8],[7]]

C [[4],[9],[3,1,0],[8],[7]]

D [[4],[9],[3,0],[8,1],[7]]

💡 Hint

Nodes in the same column are listed in order of their level from top to bottom.

Column -2 has [4], -1 has [9], 0 has [3,0,1] in level order, 1 has [8], and 2 has [7].

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Implementation

What error will this code produce when run on a non-empty binary tree?

DSA Typescript

function verticalOrderTraversal(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [[root, 0]];
  let min = 0, max = 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]);
    min = Math.min(min, col);
    max = Math.max(max, col);
  }

  const result = [];
  for (let i = min; i <= max; i++) {
    result.push(map.get(i));
  }
  return result;
}

A The traversal order is incorrect because queue.pop() removes from the end, causing depth-first behavior instead of breadth-first.

B No error; the code runs correctly and returns vertical order traversal.

C TypeError because map.get(col) returns undefined and push is called on undefined.

D SyntaxError due to missing semicolon after map.set(col, []).

💡 Hint

Consider how queue.pop() affects the order of node processing compared to queue.shift().

Using pop() removes the last element, making the traversal depth-first, which breaks the vertical order logic that requires breadth-first traversal.

🧠 Conceptual

advanced

Understanding Column Indexing in Vertical Order Traversal

In vertical order traversal, what does the column index represent and how is it assigned to nodes?

A Column index represents horizontal distance from root; root is 0, left child is parent column -1, right child is parent column +1.

B Column index represents depth level; root is 0, children increment column by 1 regardless of side.

C Column index is assigned randomly to nodes to group them vertically.

D Column index counts nodes from left to right in the same level, starting at 0.

💡 Hint

Think about how horizontal position changes when moving left or right in the tree.

Column index tracks horizontal distance from root: left child decreases column by 1, right child increases by 1.

🚀 Application

expert

Find the Vertical Order Traversal Output for Complex Tree

Given the binary tree below, what is the vertical order traversal output?

Tree structure:
10
/ \
5 15
/ \ \
3 7 18
\ /
4 16

DSA Typescript

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

function verticalOrderTraversal(root: TreeNode | null): number[][] {
  if (!root) return [];
  const map = new Map<number, number[]>();
  const queue: Array<[TreeNode, number]> = [[root, 0]];
  let min = 0, max = 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]);
    min = Math.min(min, col);
    max = Math.max(max, col);
  }

  const result: number[][] = [];
  for (let i = min; i <= max; i++) {
    result.push(map.get(i)!);
  }
  return result;
}

const root = new TreeNode(10,
  new TreeNode(5, new TreeNode(3, null, new TreeNode(4)), new TreeNode(7)),
  new TreeNode(15, null, new TreeNode(18, new TreeNode(16), null))
);
console.log(verticalOrderTraversal(root));

A [[3],[5,4],[10,7,16],[15],[18]]

B [[3],[5],[10,4,7],[15,16],[18]]

C [[3,4],[5],[10,7],[15,16],[18]]

D [[3],[5,4],[10,7],[15,16],[18]]

💡 Hint

Track column indices carefully and list nodes in each column by their level order.

Column -2 has [3], -1 has [5,4], 0 has [10,7], 1 has [15,16], 2 has [18].

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