Vertical Order Traversal of Binary Tree in DSA Javascript - Build from Scratch

Vertical Order Traversal of Binary Tree

📖 Scenario: You are working with a binary tree data structure that represents a hierarchy of tasks in a project. You want to view the tasks grouped by their vertical positions when the tree is drawn on paper.

🎯 Goal: Build a program that performs a vertical order traversal of a binary tree. The program will group nodes by their vertical columns and print the nodes in each column from top to bottom.

📋 What You'll Learn

Create a binary tree using node objects with val, left, and right properties

Use a helper variable to track the horizontal distance (column) of each node

Traverse the tree and group nodes by their column in a dictionary

Print the nodes grouped by their vertical columns in order from leftmost to rightmost

💡 Why This Matters

🌍 Real World

Vertical order traversal helps visualize hierarchical data in columns, useful in UI layouts, organizational charts, and parsing expressions.

💼 Career

Understanding tree traversals and grouping data by position is important for software engineers working with data structures, UI rendering, and algorithms.

1

Create the Binary Tree

Create a binary tree with a root node called root. The root node should have val 1, a left child with val 2, and a right child with val 3. The left child of node 2 should be a node with val 4, and the right child of node 2 should be a node with val 5.

DSA Javascript

// Create the binary tree nodes and link them
// Your code here

Hint

Use nested objects to create nodes with val, left, and right properties.

2

Set Up a Map to Store Nodes by Column

Create a variable called columnTable and set it to an empty JavaScript Map. This will store arrays of node values grouped by their column index.

DSA Javascript

const root = {
  val: 1,
  left: {
    val: 2,
    left: { val: 4, left: null, right: null },
    right: { val: 5, left: null, right: null }
  },
  right: { val: 3, left: null, right: null }
};

// Create a Map called columnTable to store nodes by their column
// Your code here

Hint

Use new Map() to create an empty map for grouping nodes.

3

Traverse the Tree and Group Nodes by Column

Write a recursive function called traverse that takes a node and its column index. If the node is not null, add its val to the array in columnTable for that column. Then call traverse on the left child with column - 1 and on the right child with column + 1. Finally, call traverse starting from root with column 0.

DSA Javascript

const root = {
  val: 1,
  left: {
    val: 2,
    left: { val: 4, left: null, right: null },
    right: { val: 5, left: null, right: null }
  },
  right: { val: 3, left: null, right: null }
};

const columnTable = new Map();

// Write a recursive function traverse(node, column) to group nodes by column
// Your code here

Hint

Use recursion to visit nodes and track their column index. Store values in columnTable.

4

Print the Vertical Order Traversal Result

Print the nodes grouped by their vertical columns in order from the smallest column index to the largest. Use Array.from(columnTable.keys()) to get all column keys, sort them, and then print the arrays of node values for each column separated by spaces.

DSA Javascript

const root = {
  val: 1,
  left: {
    val: 2,
    left: { val: 4, left: null, right: null },
    right: { val: 5, left: null, right: null }
  },
  right: { val: 3, left: null, right: null }
};

const columnTable = new Map();

function traverse(node, column) {
  if (node === null) return;
  if (!columnTable.has(column)) {
    columnTable.set(column, []);
  }
  columnTable.get(column).push(node.val);
  traverse(node.left, column - 1);
  traverse(node.right, column + 1);
}

traverse(root, 0);

// Print the vertical order traversal result
// Your code here

Hint

Sort the column keys and print the node values for each column separated by spaces.