Vertical Order Traversal of Binary Tree in DSA Javascript

Mental Model

We want to group tree nodes by their vertical columns from left to right, and list nodes top to bottom in each column.

Analogy: Imagine standing in front of a tree and looking straight at it. Nodes that line up vertically in your view belong to the same group. We collect these groups from left side to right side.

      1
     / \
    2   3
   / \   \
  4   5   6

Columns: -2  -1   0   1   2
Nodes:   4   2   1,5  3   6

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6

Goal: Group nodes by vertical columns from left to right, top to bottom in each column

Step 1: Start at root node 1 with column 0

Column 0: [1]
Columns so far: {0: [1]}

Why: Root is the center column, start grouping here

Step 2: Move to left child 2 with column -1

Column -1: [2]
Columns so far: {-1: [2], 0: [1]}

Why: Left child is one column to the left

Step 3: Move to left child 4 with column -2

Column -2: [4]
Columns so far: {-2: [4], -1: [2], 0: [1]}

Why: Left child again moves one column left

Step 4: Back to node 2, move to right child 5 with column 0

Column 0: [1, 5]
Columns so far: {-2: [4], -1: [2], 0: [1, 5]}

Why: Right child moves one column right from parent

Step 5: Back to root 1, move to right child 3 with column 1

Column 1: [3]
Columns so far: {-2: [4], -1: [2], 0: [1, 5], 1: [3]}

Why: Right child moves one column right

Step 6: Move to right child 6 of node 3 with column 2

Column 2: [6]
Columns so far: {-2: [4], -1: [2], 0: [1, 5], 1: [3], 2: [6]}

Why: Right child moves one column right

Result:

Columns from left to right:
-2: 4
-1: 2
0: 1 -> 5
1: 3
2: 6

Annotated Code

DSA Javascript

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

function verticalOrderTraversal(root) {
  if (!root) return [];
  const columnTable = new Map();
  const queue = [];
  queue.push([root, 0]); // node with its column index

  while (queue.length > 0) {
    const [node, col] = queue.shift();
    if (!columnTable.has(col)) {
      columnTable.set(col, []);
    }
    columnTable.get(col).push(node.val); // add node value to its column

    if (node.left) {
      queue.push([node.left, col - 1]); // left child column is col-1
    }
    if (node.right) {
      queue.push([node.right, col + 1]); // right child column is col+1
    }
  }

  const sortedCols = Array.from(columnTable.keys()).sort((a, b) => a - b);
  const result = [];
  for (const col of sortedCols) {
    result.push(columnTable.get(col));
  }
  return result;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3,
    null,
    new TreeNode(6)
  )
);

const output = verticalOrderTraversal(root);
for (const colNodes of output) {
  console.log(colNodes.join(' -> '));
}

queue.push([root, 0]); // node with its column index

Initialize queue with root node at column 0

const [node, col] = queue.shift();

Take next node and its column from queue for processing

if (!columnTable.has(col)) { columnTable.set(col, []); }

Create list for column if not exists

columnTable.get(col).push(node.val); // add node value to its column

Add current node value to its column group

if (node.left) { queue.push([node.left, col - 1]); }

Add left child to queue with column one less

if (node.right) { queue.push([node.right, col + 1]); }

Add right child to queue with column one more

const sortedCols = Array.from(columnTable.keys()).sort((a, b) => a - b);

Sort columns from left to right

for (const col of sortedCols) { result.push(columnTable.get(col)); }

Collect node groups in column order

Output

4

2

1 -> 5

3

6

Complexity Analysis

Time: O(n) because we visit each node once during BFS traversal

Space: O(n) because we store all nodes in the column table and queue

vs Alternative: Compared to DFS, BFS preserves top-to-bottom order naturally without extra sorting by depth

Edge Cases

Empty tree (root is null)

Returns empty list immediately

DSA Javascript

if (!root) return [];

Tree with only one node

Returns list with one column containing that single node

DSA Javascript

queue.push([root, 0]);

Tree with multiple nodes in same column

Nodes appear in order top to bottom as visited by BFS

DSA Javascript

columnTable.get(col).push(node.val);

When to Use This Pattern

When you need to group tree nodes by vertical columns and preserve top-to-bottom order, use vertical order traversal with BFS and column indexing.

Common Mistakes

Mistake: Using DFS without tracking node depth causes wrong order in columns
Fix: Use BFS to process nodes level by level to maintain top-to-bottom order

Mistake: Not sorting columns before output leads to unordered columns
Fix: Sort column keys before collecting results

Summary

Groups binary tree nodes by their vertical columns from left to right, top to bottom.

Use when you want to see nodes aligned vertically as if viewing the tree from the front.

The key is to assign column indices and use BFS to keep nodes in top-down order within each column.