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].