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

Vertical Order Traversal of Binary Tree

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to see the family members grouped by their vertical positions when you look at the tree from the front.

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

📋 What You'll Learn

Create a binary tree using a TreeNode class with val, left, and right properties

Use a queue to perform a breadth-first traversal while tracking horizontal distances

Group nodes by their vertical columns using a dictionary (Map)

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

💡 Why This Matters

🌍 Real World

Vertical order traversal helps in visualizing hierarchical data like family trees, organizational charts, or syntax trees in compilers.

💼 Career

Understanding tree traversals and grouping techniques is essential for software engineers working with data structures, databases, and UI rendering.

1

Create the Binary Tree Structure

Create a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create a binary tree with root node value 1, left child 2, right child 3, left child of 2 as 4, and right child of 2 as 5.

DSA Typescript

# Your code here

Hint

Define the TreeNode class first, then create the nodes and link them as described.

2

Set Up a Map to Store Vertical Columns

Create a variable called columnTable as a Map<number, number[]> to store arrays of node values grouped by their vertical column index. Also create two variables minColumn and maxColumn initialized to 0 to track the range of columns.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Create a Map to hold nodes by column and variables to track min and max columns
// Your code here

Hint

Use new Map() to create columnTable and initialize minColumn and maxColumn to zero.

3

Perform Vertical Order Traversal Using BFS

Create a queue called queue as an array of tuples containing a TreeNode and its column index. Initialize it with [root, 0]. Use a while loop to process nodes from the queue. For each node, add its value to columnTable at the current column. Update minColumn and maxColumn if needed. Add the left child with column - 1 and right child with column + 1 to the queue if they exist.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const columnTable = new Map();
let minColumn = 0;
let maxColumn = 0;

// Your code here

Hint

Use a queue to do breadth-first search. Track each node's column index and update the map and min/max columns accordingly.

4

Print the Vertical Order Traversal Result

Use a for loop from minColumn to maxColumn. For each column, print the array of node values from columnTable joined by ' -> '. Each column's nodes should be printed on a new line.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const columnTable = new Map();
let minColumn = 0;
let maxColumn = 0;

const queue: [TreeNode, number][] = [[root, 0]];

while (queue.length > 0) {
    const [node, column] = queue.shift()!;
    if (!columnTable.has(column)) {
        columnTable.set(column, []);
    }
    columnTable.get(column)!.push(node.val);
    minColumn = Math.min(minColumn, column);
    maxColumn = Math.max(maxColumn, column);

    if (node.left !== null) {
        queue.push([node.left, column - 1]);
    }
    if (node.right !== null) {
        queue.push([node.right, column + 1]);
    }
}

// Your code here

Hint

Loop from minColumn to maxColumn and print the values joined by arrows.