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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Vertical Order Traversal for a Simple Tree

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

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

Assume vertical order traversal groups nodes by their horizontal distance from root, from left to right, and within each group nodes are listed top to bottom.

DSA Javascript

class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function verticalOrderTraversal(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  let minHd = 0, maxHd = 0;

  while (queue.length) {
    const { node, hd } = queue.shift();
    if (!map.has(hd)) map.set(hd, []);
    map.get(hd).push(node.val);
    if (node.left) queue.push({ node: node.left, hd: hd - 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1 });
    minHd = Math.min(minHd, hd);
    maxHd = Math.max(maxHd, hd);
  }

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

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

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

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

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

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

💡 Hint

Think about horizontal distances: left child decreases hd by 1, right child increases hd by 1.

Nodes are grouped by horizontal distance (hd). Node 2 is at hd -1, node 1 and 4 at hd 0, node 3 at hd 1, and node 5 at hd 2. So the vertical order is [[2], [1, 4], [3], [5]].

🧠 Conceptual

intermediate

Understanding Horizontal Distance in Vertical Order Traversal

In vertical order traversal of a binary tree, what does the horizontal distance (hd) represent?

A The number of nodes in the subtree rooted at that node

B The vertical level of a node from the root

C The depth of a node in the tree

D The horizontal position of a node relative to the root, where left child decreases hd by 1 and right child increases hd by 1

💡 Hint

Think about how left and right children affect horizontal position.

Horizontal distance is a measure of how far left or right a node is from the root. Left child decreases hd by 1, right child increases hd by 1.

❓ Predict Output

advanced

Output of Vertical Order Traversal with Multiple Nodes at Same Position

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

Tree structure:
1
/ \ > 2 3
/ \ \ > 4 5 6
\
7

Nodes at the same horizontal distance and level should be listed in order of appearance from left to right.

DSA Javascript

class Node {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function verticalOrderTraversal(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0, level: 0 }];
  let minHd = 0, maxHd = 0;

  while (queue.length) {
    const { node, hd, level } = queue.shift();
    if (!map.has(hd)) map.set(hd, []);
    map.get(hd).push({ val: node.val, level });
    if (node.left) queue.push({ node: node.left, hd: hd - 1, level: level + 1 });
    if (node.right) queue.push({ node: node.right, hd: hd + 1, level: level + 1 });
    minHd = Math.min(minHd, hd);
    maxHd = Math.max(maxHd, hd);
  }

  const result = [];
  for (let i = minHd; i <= maxHd; i++) {
    const arr = map.get(i);
    arr.sort((a, b) => a.level - b.level);
    result.push(arr.map(x => x.val));
  }
  return result;
}

const root = new Node(1, new Node(2, new Node(4), new Node(5, null, new Node(7))), new Node(3, null, new Node(6)));
console.log(verticalOrderTraversal(root));

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

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

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

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

💡 Hint

Remember to sort nodes by their level within each horizontal distance group.

At hd=0, nodes 1 (level 0), 5 (level 2), and 7 (level 3) appear. They are sorted by level: 1, 5, then 7. Other groups follow similarly.

🔧 Debug

advanced

Identify the Error in Vertical Order Traversal Code

The following code attempts to perform vertical order traversal but produces incorrect output. What is the main error?

Code snippet:

function verticalOrderTraversal(root) {
  if (!root) return [];
  const map = new Map();
  const queue = [{ node: root, hd: 0 }];
  while (queue.length) {
    const { node, hd } = queue.shift();
    if (!map.has(hd)) map.set(hd, []);
    map.get(hd).push(node.val);
    if (node.left) queue.push({ node: node.left, hd: hd + 1 });
    if (node.right) queue.push({ node: node.right, hd: hd - 1 });
  }
  return Array.from(map.values());
}

A The map should store nodes by level, not horizontal distance

B The horizontal distance for left and right children is swapped; left should decrease hd, right should increase hd

C The queue should use a stack to maintain correct order

D The function should return map.keys() instead of map.values()

💡 Hint

Check how horizontal distance changes for left and right children.

Left child should have hd - 1, right child hd + 1. The code swaps these, causing incorrect grouping.

🚀 Application

expert

Number of Vertical Lines in a Complex Binary Tree

Given the binary tree below, how many vertical lines (unique horizontal distances) will the vertical order traversal produce?

Tree structure:
10
/ \ > 7 15
/ \ \ > 5 8 20
/ / \ > 3 17 25
\ > 18

Count the number of unique horizontal distances from the root node.

A 8

B 6

C 7

D 5

💡 Hint

Track horizontal distance changes from root to each node.

Horizontal distances range from -3 (node 3) to +3 (node 25), inclusive, totaling 7 unique vertical lines.

Practice

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

easy

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

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

C. Nodes are grouped by their horizontal rows from top to bottom.

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

Solution

1. Step 1: Understand vertical columns in a binary tree

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

2. Step 2: Identify traversal order

   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 D

4. Quick Check:

   Vertical order = group by columns [OK]

Hint: Think columns, not rows or preorder traversal [OK]

Common Mistakes:

• Confusing vertical order with level order traversal
• Thinking vertical order is preorder or inorder traversal
• Mixing horizontal rows with vertical columns

2. Which of the following JavaScript code snippets correctly initializes a map to store vertical order nodes by column?

easy

A. const map = new Map();

B. const map = {};

C. const map = new Set();

D. const map = [];

Solution

1. Step 1: Identify suitable data structure for key-value pairs

   We need to map column numbers (keys) to arrays of nodes (values), so Map is ideal.

2. Step 2: Check each option

   const map = new Map(); uses Map which supports keys of any type and preserves insertion order. const map = {}; is an object but less flexible for numeric keys. const map = new Set(); is a Set, which stores unique values without keys. const map = []; is an array, not suitable for key-value mapping.

3. Final Answer:

   const map = new Map(); -> Option A

4. Quick Check:

   Use Map for column to nodes mapping [OK]

Hint: Use Map for flexible key-value storage [OK]

Common Mistakes:

• Using Set instead of Map for key-value pairs
• Using array instead of Map for mapping columns
• Using plain object which may cause key type issues

3. Given the binary tree:

    1
   / \
  2   3
 / \   \
4   5   6

What is the vertical order traversal output?

medium

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

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

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

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

Solution

1. Step 1: Assign column indices to nodes

   Root (1) is column 0. Left child decreases column by 1, right child increases by 1.
   So, 4 is at -2, 2 at -1, 1 and 5 at 0, 3 at 1, 6 at 2.

2. Step 2: Group nodes by columns and list them top to bottom

   Columns: -2: [4], -1: [2], 0: [1,5], 1: [3], 2: [6]

3. Final Answer:

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

4. Quick Check:

   Column grouping matches answer A [OK]

Hint: Track column index: left -1, right +1 [OK]

Common Mistakes:

• Mixing node order within the same column
• Ignoring column indices and grouping by levels
• Swapping left and right child column adjustments

4. Consider this code snippet for vertical order traversal:

function verticalOrder(root) {
  const map = new Map();
  function dfs(node, col) {
    if (!node) return;
    dfs(node.left, col - 1);
    dfs(node.right, col + 1);
    if (!map.has(col)) map.set(col, []);
    map.get(col).push(node.val);
  }
  dfs(root, 0);
  return [...map.values()];
}

What is the main issue with this code?

medium

A. The function does not handle empty trees.

B. Map keys should be strings, not numbers.

C. DFS does not guarantee top-to-bottom order in vertical columns.

D. The code uses recursion incorrectly.

Solution

1. Step 1: Understand DFS traversal order

   DFS explores depth first, so nodes deeper in the tree may be visited before nodes higher up in the same column.

2. Step 2: Identify vertical order requirement

   Vertical order requires nodes in each column to be output top to bottom, which DFS alone does not guarantee.

3. Final Answer:

   DFS does not guarantee top-to-bottom order in vertical columns. -> Option C

4. Quick Check:

   DFS order ≠ vertical top-to-bottom order [OK]

Hint: Use BFS for correct vertical top-to-bottom order [OK]

Common Mistakes:

• Assuming DFS preserves vertical order top-to-bottom
• Thinking Map keys must be strings
• Ignoring empty tree base case (which is handled here)

5. You want to perform vertical order traversal of a binary tree where nodes in the same column and row are sorted by value ascending. Which approach correctly achieves this?

hard

A. Use DFS and store nodes in a map by column only, then output map values.

B. Use BFS with a queue storing nodes with their row and column, then sort nodes by column, row, and value.

C. Traverse tree inorder and group nodes by column index only.

D. Use BFS but ignore row information and output nodes by column only.

Solution

1. Step 1: Understand sorting requirements

   Nodes must be sorted by column, then row (top to bottom), then by node value ascending if same row and column.

2. Step 2: Choose traversal and data structure

   BFS with queue tracks nodes level by level (row), and storing column and row allows sorting by these keys plus value.

3. Step 3: Why other options fail

   DFS does not guarantee row order. Inorder traversal does not track columns properly. Ignoring row info loses sorting order.

4. Final Answer:

   Use BFS with a queue storing nodes with their row and column, then sort nodes by column, row, and value. -> Option B

5. Quick Check:

   BFS + sort by col, row, value = correct order [OK]

Hint: Track row and column with BFS, then sort by col, row, value [OK]

Common Mistakes:

• Using DFS which loses row order
• Not sorting nodes by value when row and column are same
• Ignoring row info in BFS