Zigzag Level Order Traversal in DSA Javascript - 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 level by level, but alternate the direction of visiting each level. For example, visit the first generation from left to right, the second from right to left, the third from left to right again, and so on.

🎯 Goal: Build a program that performs a zigzag level order traversal on a binary tree and returns the values of nodes in the zigzag order.

📋 What You'll Learn

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

Use a variable result to store the zigzag order traversal as a list of lists

Use a boolean variable leftToRight to track the direction of traversal for each level

Implement the zigzag level order traversal using a queue and alternate the direction of adding node values

Print the final result array

💡 Why This Matters

🌍 Real World

Zigzag traversal is useful in scenarios like printing organizational charts or family trees where alternating direction improves readability.

💼 Career

Understanding tree traversals and how to manipulate data structures is essential for software engineering roles involving algorithms, data processing, and system design.

1

Create the binary tree nodes

Create a class called TreeNode with a constructor that takes val, left, and right parameters. Then create the following tree nodes and connect them to form this tree:

1
/ \
2 3
/ \ \
4 5 6

Create variables root, node2, node3, node4, node5, and node6 with these exact values and connections.

DSA Javascript

# Define TreeNode class and create tree nodes
# Your code here

Hint

Define the TreeNode class first. Then create leaf nodes node4, node5, and node6. Finally, create node2 and node3 connecting the leaf nodes, and then root connecting node2 and node3.

2

Setup variables for traversal

Create a variable called result and set it to an empty array []. Create a variable called queue and set it to an array containing only root. Create a boolean variable called leftToRight and set it to true to track the direction of traversal.

DSA Javascript

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

const node4 = new TreeNode(4);
const node5 = new TreeNode(5);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node4, node5);
const node3 = new TreeNode(3, null, node6);
const root = new TreeNode(1, node2, node3);

// Create result array, queue with root, and leftToRight boolean
# Your code here

Hint

Initialize result as an empty array to store levels. Put root inside queue to start traversal. Use leftToRight boolean to switch directions.

3

Implement zigzag level order traversal

Use a while loop that runs while queue.length is greater than 0. Inside the loop, create a variable levelSize set to queue.length. Create an empty array levelNodes. Use a for loop from i = 0 to i < levelSize. In each iteration, remove the first node from queue into a variable currentNode. If leftToRight is true, push currentNode.val to levelNodes. Otherwise, insert currentNode.val at the start of levelNodes. If currentNode.left exists, push it to queue. If currentNode.right exists, push it to queue. After the for loop, push levelNodes to result. Toggle leftToRight to its opposite value.

DSA Javascript

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

const node4 = new TreeNode(4);
const node5 = new TreeNode(5);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node4, node5);
const node3 = new TreeNode(3, null, node6);
const root = new TreeNode(1, node2, node3);

const result = [];
const queue = [root];
let leftToRight = true;

// Implement zigzag traversal using while and for loops
# Your code here

Hint

Use a while loop to process each level. Use queue.shift() to get nodes. Use push or unshift on levelNodes depending on leftToRight. Add children to queue. Toggle leftToRight after each level.

4

Print the zigzag traversal result

Write a console.log statement to print the result array.

DSA Javascript

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

const node4 = new TreeNode(4);
const node5 = new TreeNode(5);
const node6 = new TreeNode(6);
const node2 = new TreeNode(2, node4, node5);
const node3 = new TreeNode(3, null, node6);
const root = new TreeNode(1, node2, node3);

const result = [];
const queue = [root];
let leftToRight = true;

while (queue.length > 0) {
    const levelSize = queue.length;
    const levelNodes = [];
    for (let i = 0; i < levelSize; i++) {
        const currentNode = queue.shift();
        if (leftToRight) {
            levelNodes.push(currentNode.val);
        } else {
            levelNodes.unshift(currentNode.val);
        }
        if (currentNode.left) queue.push(currentNode.left);
        if (currentNode.right) queue.push(currentNode.right);
    }
    result.push(levelNodes);
    leftToRight = !leftToRight;
}

// Print the result array
# Your code here

Hint

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