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.