0094_binary_tree_inorder_traversal.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 Inorder Traversal - LeetCode 94</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">#94</span> Binary Tree Inorder Traversal</h1>
            <p>Return the inorder traversal of a binary tree's values (Left → Root → Right).</p>
            <div class="problem-meta">
                <span class="meta-tag">Tree</span>
                <span class="meta-tag">Stack</span>
                <span class="meta-tag">Easy</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0094_binary_tree_inorder_traversal/0094_binary_tree_inorder_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="400"></svg>
            <div class="status-message" id="status">Click "Step" for inorder traversal</div>
        </div>

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

"""
LeetCode Binary Tree Inorder Traversal

Problem from LeetCode: https://leetcode.com/problems/binary-tree-inorder-traversal/

Description:
Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]

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

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

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

class Solution:
    def inorder_traversal(self, root: Optional[TreeNode]) -&gt; List[int]:
        """
        Perform an inorder traversal of a binary tree (recursive approach).
        Inorder: left -&gt; root -&gt; right
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[int]: Inorder traversal values
        """
        result = []
        self._inorder_helper(root, result)
        return result
        
    def _inorder_helper(self, node: Optional[TreeNode], result: List[int]) -&gt; None:
        """Helper function for recursive inorder traversal."""
        if not node:
            return
            
        # Traverse left subtree
        self._inorder_helper(node.left, result)
        
        # Visit the node
        result.append(node.val)
        
        # Traverse right subtree
        self._inorder_helper(node.right, result)
    
    def inorder_traversal_iterative(self, root: Optional[TreeNode]) -&gt; List[int]:
        """
        Perform an inorder traversal of a binary tree (iterative approach).
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[int]: Inorder traversal values
        """
        result = []
        stack = []
        current = root
        
        while current or stack:
            # Traverse to the leftmost node
            while current:
                stack.append(current)
                current = current.left
                
            # Visit the node at the top of the stack
            current = stack.pop()
            result.append(current.val)
            
            # Move to the right subtree
            current = current.right
            
        return result
    
    def inorder_traversal_morris(self, root: Optional[TreeNode]) -&gt; List[int]:
        """
        Perform an inorder traversal using Morris Traversal.
        This approach uses O(1) extra space and doesn't use recursion or a stack.
        
        Args:
            root: Root of the binary tree
            
        Returns:
            List[int]: Inorder traversal values
        """
        result = []
        current = root
        
        while current:
            # If there is no left child, visit the node and go right
            if not current.left:
                result.append(current.val)
                current = current.right
            else:
                # Find the inorder predecessor (rightmost node in left subtree)
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                
                # If right pointer is null, make it point to current
                # This creates a temporary link to get back to the root
                if not predecessor.right:
                    predecessor.right = current
                    current = current.left
                else:
                    # Revert the change made in the above step
                    predecessor.right = None
                    result.append(current.val)
                    current = current.right
                    
        return result

# Helper function to create a binary tree from a list of values
def create_tree(values):
    if not values:
        return None
    
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    
    while queue and i &lt; len(values):
        node = queue.pop(0)
        
        # Left child
        if i &lt; len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        
        # 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
    # Tree:
    #   1
    #    \
    #     2
    #    /
    #   3
    root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    result1 = solution.inorder_traversal(root1)
    print(f"Example 1: {result1}")  # Expected output: [1, 3, 2]
    
    # Example 2
    root2 = None
    result2 = solution.inorder_traversal(root2)
    print(f"Example 2: {result2}")  # Expected output: []
    
    # Example 3
    root3 = TreeNode(1)
    result3 = solution.inorder_traversal(root3)
    print(f"Example 3: {result3}")  # Expected output: [1]
    
    # Additional example
    # Tree:
    #     1
    #    / \
    #   2   3
    #  / \
    # 4   5
    root4 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    result4 = solution.inorder_traversal(root4)
    print(f"Example 4: {result4}")  # Expected output: [4, 2, 5, 1, 3]
    
    # Compare with iterative and Morris traversal
    print("\nUsing iterative approach:")
    print(f"Example 1: {solution.inorder_traversal_iterative(root1)}")
    print(f"Example 4: {solution.inorder_traversal_iterative(root4)}")
    
    print("\nUsing Morris traversal:")
    print(f"Example 1: {solution.inorder_traversal_morris(root1)}")
    print(f"Example 4: {solution.inorder_traversal_morris(root4)}")
</pre>
            </div>
        </div>
    </div>

    <script>
        const tree = {
            val: 1, id: 'root',
            left: null,
            right: { val: 2, id: 'right',
                left: { val: 3, id: 'right-left', left: null, right: null },
                right: null
            }
        };

        let stack = [];
        let current = tree;
        let result = [];
        let nodeStates = {};
        let phase = 'go_left';

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

        function drawTree(node, x, y, dx, path) {
            if (!node) return;

            const r = 25;
            const state = nodeStates[path] || 'unvisited';

            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, path + '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, path + 'R');
            }

            let fill = "#e3f2fd", stroke = "#1976d2";
            if (state === 'current') { fill = "#fef3c7"; stroke = "#f59e0b"; }
            else if (state === 'instack') { fill = "#fff3e0"; stroke = "#ff9800"; }
            else if (state === 'visited') { 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", "18px")
                .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("Inorder Traversal: Left → Root → Right");

            drawTree(tree, width/2, 70, 80, 'root');

            // Stack
            svg.append("text").attr("x", 30).attr("y", 250).attr("font-weight", "bold").text("Stack:");
            stack.forEach((item, idx) => {
                svg.append("rect").attr("x", 90 + idx * 50).attr("y", 235)
                    .attr("width", 45).attr("height", 30).attr("rx", 5)
                    .attr("fill", "#fff3e0").attr("stroke", "#ff9800");
                svg.append("text").attr("x", 112 + idx * 50).attr("y", 255)
                    .attr("text-anchor", "middle").attr("font-weight", "bold").text(item.val);
            });

            // Result
            svg.append("text").attr("x", 30).attr("y", 310).attr("font-weight", "bold").text("Result:");
            result.forEach((val, idx) => {
                svg.append("rect").attr("x", 100 + idx * 50).attr("y", 295)
                    .attr("width", 45).attr("height", 30).attr("rx", 5)
                    .attr("fill", "#d1fae5").attr("stroke", "#10b981");
                svg.append("text").attr("x", 122 + idx * 50).attr("y", 315)
                    .attr("text-anchor", "middle").attr("font-weight", "bold").text(val);
            });

            // Legend
            const legend = [{c: "#fef3c7", t: "Current"}, {c: "#fff3e0", t: "In Stack"}, {c: "#d1fae5", t: "Visited"}];
            legend.forEach((l, i) => {
                svg.append("rect").attr("x", 30 + i * 100).attr("y", 355)
                    .attr("width", 18).attr("height", 18).attr("fill", l.c).attr("stroke", "#999");
                svg.append("text").attr("x", 55 + i * 100).attr("y", 368).attr("font-size", "12px").text(l.t);
            });
        }

        function getPath(node, target, path = 'root') {
            if (!node) return null;
            if (node === target) return path;
            return getPath(node.left, target, path + 'L') || getPath(node.right, target, path + 'R');
        }

        function step() {
            if (!current && stack.length === 0) {
                document.getElementById("status").textContent = `Done! Inorder: [${result.join(", ")}]`;
                return false;
            }

            if (phase === 'go_left') {
                if (current) {
                    const path = getPath(tree, current);
                    nodeStates[path] = 'instack';
                    stack.push(current);
                    document.getElementById("status").textContent = `Push ${current.val} to stack, go left`;
                    current = current.left;
                } else {
                    phase = 'process';
                }
            } else if (phase === 'process') {
                current = stack.pop();
                const path = getPath(tree, current);
                nodeStates[path] = 'visited';
                result.push(current.val);
                document.getElementById("status").textContent = `Pop and visit ${current.val}`;
                current = current.right;
                phase = 'go_left';
            }

            draw();
            return current || stack.length > 0;
        }

        function reset() {
            stack = []; current = tree; result = []; nodeStates = {}; phase = 'go_left';
            if (autoTimer) clearInterval(autoTimer);
            autoRunning = false;
            document.getElementById("autoBtn").textContent = "Auto Run";
            document.getElementById("status").textContent = 'Click "Step" for inorder 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"; } }, 800);
            }
        }

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