0103_binary_tree_zigzag_level_order.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Binary Tree Zigzag Level Order - LeetCode 103</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#103</span> Binary Tree Zigzag Level Order Traversal</h1>
            <p>Return the zigzag level order traversal (alternating left-right, right-left).</p>
            <div class="problem-meta">
                <span class="meta-tag">Tree</span>
                <span class="meta-tag">BFS</span>
                <span class="meta-tag">Medium</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0103_binary_tree_zigzag_level_order_traversal/0103_binary_tree_zigzag_level_order_traversal.py</code>
            </div>

        </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Tree traversal is like <strong>exploring a family tree</strong>:</p>
            <ul>
                <li><strong>Root:</strong> Start at the top node</li>
                <li><strong>Recurse:</strong> Visit left and right children</li>
                <li><strong>Base case:</strong> Stop at null/leaf nodes</li>
                <li><strong>Combine:</strong> Build answer from subtree results</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            <div class="controls">
                <button id="stepBtn">Step</button>
                <button id="autoBtn">Auto Run</button>
                <button id="resetBtn">Reset</button>
            </div>
            <svg id="mainSvg" width="700" height="420"></svg>
            <div class="status-message" id="status">Click "Step" for zigzag traversal</div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List, Optional
from collections import deque


"""
LeetCode Binary Tree Zigzag Level Order Traversal

Problem from LeetCode: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Description:
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.
(i.e., from left to right, then right to left for the next level and alternate between).

Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:
Input: root = [1]
Output: [[1]]

Example 3:
Input: root = []
Output: []
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def zigzag_level_order(self, root: Optional[TreeNode]) -&gt; List[List[int]]:
        """
        Return the zigzag level order traversal of a binary tree's values.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[List[int]]: Zigzag level order traversal
        """
        if not root:
            return []
            
        result = []
        queue = deque([root])
        left_to_right = True
        
        while queue:
            level_size = len(queue)
            level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Add the level values in zigzag order
            if not left_to_right:
                level.reverse()
                
            result.append(level)
            left_to_right = not left_to_right
            
        return result
    
    def zigzag_level_order_alternative(self, root: Optional[TreeNode]) -&gt; List[List[int]]:
        """
        Alternative implementation using a deque for each level.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[List[int]]: Zigzag level order traversal
        """
        if not root:
            return []
            
        result = []
        queue = deque([root])
        left_to_right = True
        
        while queue:
            level_size = len(queue)
            level = deque()
            
            for _ in range(level_size):
                node = queue.popleft()
                
                # Add values in zigzag order using a deque
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                    
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(list(level))
            left_to_right = not left_to_right
            
        return result
    
    def zigzag_level_order_dfs(self, root: Optional[TreeNode]) -&gt; List[List[int]]:
        """
        DFS-based implementation for zigzag level order traversal.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[List[int]]: Zigzag level order traversal
        """
        result = []
        
        def dfs(node, level):
            if not node:
                return
                
            # Add new level if needed
            if len(result) &lt;= level:
                result.append([])
                
            # Add node value to the current level
            result[level].append(node.val)
            
            # Process children
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
        
        dfs(root, 0)
        
        # Reverse alternate levels for zigzag ordering
        for i in range(1, len(result), 2):
            result[i].reverse()
            
        return result

# Helper function to create a binary tree from level order list
def create_tree(values):
    if not values:
        return None
        
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    
    while queue and i &lt; len(values):
        node = queue.popleft()
        
        # Add left child
        if i &lt; len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        
        # Add right child
        if i &lt; len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
        
    return root

if __name__ == '__main__':
    # Example usage based on LeetCode sample
    solution = Solution()
    
    # Example 1
    root1 = create_tree([3, 9, 20, None, None, 15, 7])
    result1 = solution.zigzag_level_order(root1)
    print(f"Example 1: {result1}")  # Expected output: [[3],[20,9],[15,7]]
    
    # Example 2
    root2 = create_tree([1])
    result2 = solution.zigzag_level_order(root2)
    print(f"Example 2: {result2}")  # Expected output: [[1]]
    
    # Example 3
    root3 = create_tree([])
    result3 = solution.zigzag_level_order(root3)
    print(f"Example 3: {result3}")  # Expected output: []
    
    # Compare with alternative implementations
    print("\nUsing alternative implementation:")
    print(f"Example 1: {solution.zigzag_level_order_alternative(root1)}")
    
    print("\nUsing DFS-based implementation:")
    print(f"Example 1: {solution.zigzag_level_order_dfs(root1)}")
</pre>
            </div>
        </div>
    </div>

    <script>
        const tree = {
            val: 3,
            left: { val: 9, left: null, right: null },
            right: { val: 20, left: { val: 15, left: null, right: null }, right: { val: 7, left: null, right: null } }
        };

        let queue = [];
        let result = [];
        let currentLevel = [];
        let leftToRight = true;
        let levelNum = 0;
        let visitedNodes = new Set();

        const width = 700, height = 420;
        const svg = d3.select("#mainSvg");
        let autoTimer = null, autoRunning = false;

        function drawTree(node, x, y, dx, id) {
            if (!node) return;
            const r = 25;

            if (node.left) {
                svg.append("line").attr("x1", x).attr("y1", y + r)
                    .attr("x2", x - dx).attr("y2", y + 60 - r)
                    .attr("stroke", "#ccc").attr("stroke-width", 2);
                drawTree(node.left, x - dx, y + 60, dx / 2, id + 'L');
            }
            if (node.right) {
                svg.append("line").attr("x1", x).attr("y1", y + r)
                    .attr("x2", x + dx).attr("y2", y + 60 - r)
                    .attr("stroke", "#ccc").attr("stroke-width", 2);
                drawTree(node.right, x + dx, y + 60, dx / 2, id + 'R');
            }

            let fill = "#e3f2fd", stroke = "#1976d2";
            if (queue.some(q => q.id === id)) { fill = "#fef3c7"; stroke = "#f59e0b"; }
            if (visitedNodes.has(id)) { fill = "#d1fae5"; stroke = "#10b981"; }

            svg.append("circle").attr("cx", x).attr("cy", y).attr("r", r)
                .attr("fill", fill).attr("stroke", stroke).attr("stroke-width", 2);
            svg.append("text").attr("x", x).attr("y", y + 6)
                .attr("text-anchor", "middle").attr("font-size", "16px")
                .attr("font-weight", "bold").text(node.val);
        }

        function draw() {
            svg.selectAll("*").remove();

            svg.append("text").attr("x", width/2).attr("y", 25)
                .attr("text-anchor", "middle").attr("font-weight", "bold")
                .text("Zigzag Level Order Traversal");

            drawTree(tree, width/2, 60, 100, 'root');

            // Direction indicator
            svg.append("text").attr("x", width/2).attr("y", 220)
                .attr("text-anchor", "middle").attr("font-size", "14px")
                .attr("fill", "#666")
                .text(`Level ${levelNum}: ${leftToRight ? "→ Left to Right" : "← Right to Left"}`);

            // Queue
            svg.append("text").attr("x", 30).attr("y", 260).attr("font-weight", "bold").text("Queue:");
            queue.forEach((item, idx) => {
                svg.append("rect").attr("x", 90 + idx * 50).attr("y", 245)
                    .attr("width", 45).attr("height", 30).attr("rx", 5)
                    .attr("fill", "#fef3c7").attr("stroke", "#f59e0b");
                svg.append("text").attr("x", 112 + idx * 50).attr("y", 265)
                    .attr("text-anchor", "middle").attr("font-weight", "bold").text(item.node.val);
            });

            // Result
            svg.append("text").attr("x", 30).attr("y", 310).attr("font-weight", "bold").text("Result:");
            let rx = 100;
            result.forEach((level, lidx) => {
                svg.append("text").attr("x", rx).attr("y", 330 + lidx * 35)
                    .attr("font-size", "14px")
                    .text(`[${level.join(", ")}]`);
            });
        }

        function step() {
            if (queue.length === 0 && result.length > 0) {
                document.getElementById("status").textContent = `Done! Result: [${result.map(l => `[${l}]`).join(", ")}]`;
                return false;
            }

            if (queue.length === 0 && result.length === 0) {
                queue.push({ node: tree, id: 'root' });
                document.getElementById("status").textContent = "Starting with root node";
                draw();
                return true;
            }

            // Process entire level
            const levelSize = queue.length;
            currentLevel = [];
            
            for (let i = 0; i < levelSize; i++) {
                const { node, id } = queue.shift();
                visitedNodes.add(id);
                currentLevel.push(node.val);

                if (node.left) queue.push({ node: node.left, id: id + 'L' });
                if (node.right) queue.push({ node: node.right, id: id + 'R' });
            }

            if (!leftToRight) currentLevel.reverse();
            result.push([...currentLevel]);

            document.getElementById("status").textContent = 
                `Level ${levelNum} (${leftToRight ? "L→R" : "R→L"}): [${currentLevel.join(", ")}]`;

            leftToRight = !leftToRight;
            levelNum++;
            draw();
            return queue.length > 0;
        }

        function reset() {
            queue = []; result = []; currentLevel = []; leftToRight = true; levelNum = 0; visitedNodes = new Set();
            if (autoTimer) clearInterval(autoTimer);
            autoRunning = false;
            document.getElementById("autoBtn").textContent = "Auto Run";
            document.getElementById("status").textContent = 'Click "Step" for zigzag traversal';
            draw();
        }

        function autoRun() {
            if (autoRunning) { clearInterval(autoTimer); autoRunning = false; document.getElementById("autoBtn").textContent = "Auto Run"; }
            else {
                autoRunning = true; document.getElementById("autoBtn").textContent = "Pause";
                autoTimer = setInterval(() => { if (!step()) { clearInterval(autoTimer); autoRunning = false; document.getElementById("autoBtn").textContent = "Auto Run"; } }, 1000);
            }
        }

        document.getElementById("stepBtn").addEventListener("click", step);
        document.getElementById("autoBtn").addEventListener("click", autoRun);
        document.getElementById("resetBtn").addEventListener("click", reset);
        reset();
    </script>
</body>
</html>