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.