Zigzag Level Order Traversal in DSA Typescript - Build from Scratch

Zigzag Level Order Traversal

📖 Scenario: Imagine you have a family tree represented as a binary tree. You want to visit each generation, but in a zigzag way: first generation from left to right, second from right to left, and so on. This helps you see the family members in a fun, alternating order.

🎯 Goal: Build a TypeScript program that performs a zigzag level order traversal on a binary tree. The program will output the values of nodes level by level, alternating the direction of traversal at each level.

📋 What You'll Learn

Create a binary tree using the given TreeNode class

Use a variable to track the current level number

Implement the zigzag level order traversal using a queue and alternating direction

Print the final traversal result as an array of arrays

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like displaying hierarchical data with alternating directions for better readability, such as organizational charts or family trees.

💼 Career

Understanding tree traversals and queue usage is essential for software engineering roles involving data structures, algorithms, and problem solving.

1

Create the binary tree structure

Create the binary tree nodes using the TreeNode class and build the tree with root value 1, left child 2, right child 3, left child of 2 as 4, and right child of 3 as 5. Assign the root node to a variable called root.

DSA Typescript

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

// Create the binary tree nodes and assign to root
// Your code here

Hint

Use the new TreeNode(value, leftChild, rightChild) constructor to build the tree step by step.

2

Add a variable to track the current level

Create a variable called level and set it to 0. This will help track which level we are currently processing in the tree.

DSA Typescript

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

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), null),
    new TreeNode(3, null, new TreeNode(5))
);

// Create a variable called level and set it to 0
// Your code here

Hint

Use let level = 0; to create the variable.

3

Implement zigzag level order traversal

Write the core logic to perform zigzag level order traversal. Use a queue called queue initialized with root. Use a while loop that runs while queue.length > 0. Inside the loop, create an array currentLevel to hold node values for the current level. Use a for loop to process all nodes at the current level. Add their children to the queue. If level is odd, reverse currentLevel before adding it to the result array result. Increment level by 1 after each level is processed. Store the final traversal in a variable called result.

DSA Typescript

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

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), null),
    new TreeNode(3, null, new TreeNode(5))
);

let level = 0;

// Implement zigzag level order traversal and store in result
// Your code here

Hint

Use a queue to process nodes level by level. Reverse the current level array when the level number is odd.

4

Print the zigzag traversal result

Write a console.log statement to print the result array which contains the zigzag level order traversal of the tree.

DSA Typescript

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

const root = new TreeNode(1,
    new TreeNode(2, new TreeNode(4), null),
    new TreeNode(3, null, new TreeNode(5))
);

let level = 0;
const result: number[][] = [];
const queue: TreeNode[] = [];
if (root !== null) {
    queue.push(root);
}

while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];
    for (let i = 0; i < levelSize; i++) {
        const node = queue.shift()!;
        currentLevel.push(node.val);
        if (node.left !== null) queue.push(node.left);
        if (node.right !== null) queue.push(node.right);
    }
    if (level % 2 === 1) {
        currentLevel.reverse();
    }
    result.push(currentLevel);
    level++;
}

// Print the result array
// Your code here

Hint

Use console.log(result); to display the final zigzag traversal.