Binary Tree Inorder Traversal in JavaScript (Time Complexity: O(n))

## Understanding the Problem In this problem, we are given a binary tree and we need to return the inorder traversal of its nodes' values. Inorder traversal is a depth-first traversal method where we visit the left subtree, the root node, and then the right subtree. ### Core Challenge The main challenge is to correctly implement the inorder traversal, especially iteratively, as the recursive solution is straightforward. ### Significance and Applications Inorder traversal is significant in various applications such as: - Binary Search Trees (BST) where inorder traversal gives nodes in non-decreasing order. - Expression trees where inorder traversal can be used to get the infix expression. ### Potential Pitfalls - Forgetting to visit nodes in the correct order. - Handling null nodes incorrectly. - Managing the stack correctly in the iterative approach. ## Approach ### Naive Solution: Recursive Approach The recursive approach is straightforward: 1. Traverse the left subtree. 2. Visit the root node. 3. Traverse the right subtree. #### Limitations - Uses the call stack which can lead to stack overflow for very deep trees. ### Optimized Solution: Iterative Approach To avoid the limitations of recursion, we can use an explicit stack to simulate the call stack. #### Thought Process 1. Use a stack to keep track of nodes. 2. Start from the root and push all left children to the stack. 3. Pop from the stack, visit the node, and push its right child and all its left children. ### Algorithm #### Recursive Approach 1. Define a helper function to perform the inorder traversal. 2. Call the helper function with the root node. #### Iterative Approach 1. Initialize an empty stack and a pointer to the root node. 2. While there are nodes to be processed: - Push all left children to the stack. - Pop from the stack, visit the node, and push its right child and all its left children. ## Code Implementation ### Recursive Solution

// Definition for a binary tree node.
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

// Recursive inorder traversal
function inorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (node === null) return;
        traverse(node.left); // Visit left subtree
        result.push(node.val); // Visit root
        traverse(node.right); // Visit right subtree
    }
    
    traverse(root);
    return result;
}

### Iterative Solution

// Iterative inorder traversal
function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        // Reach the leftmost node of the current node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        // Current must be null at this point
        current = stack.pop();
        result.push(current.val); // Visit the node
        
        // We have visited the node and its left subtree. Now, it's right subtree's turn
        current = current.right;
    }
    
    return result;
}

## Complexity Analysis ### Recursive Approach - **Time Complexity**: O(n) - We visit each node exactly once. - **Space Complexity**: O(h) - The height of the tree, due to the call stack. ### Iterative Approach - **Time Complexity**: O(n) - We visit each node exactly once. - **Space Complexity**: O(h) - The height of the tree, due to the explicit stack. ## Edge Cases - An empty tree (root is null). - A tree with only one node. - A tree where all nodes are either left children or right children. ### Example Edge Cases 1. **Empty Tree**: - Input: `[]` - Output: `[]` 2. **Single Node**: - Input: `[1]` - Output: `[1]` 3. **All Left Children**: - Input: `[3, 2, null, 1]` - Output: `[1, 2, 3]` ## Testing To test the solution comprehensively: 1. Test with an empty tree. 2. Test with a single node. 3. Test with a balanced tree. 4. Test with a skewed tree (all left or all right children). ### Example Test Cases

// Test cases
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3)));
console.log(inorderTraversal(root1)); // [1, 3, 2]

const root2 = null;
console.log(inorderTraversal(root2)); // []

const root3 = new TreeNode(1);
console.log(inorderTraversal(root3)); // [1]

const root4 = new TreeNode(3, new TreeNode(2, new TreeNode(1)));
console.log(inorderTraversal(root4)); // [1, 2, 3]

## Thinking and Problem-Solving Tips - Break down the problem into smaller parts. - Understand the traversal order and ensure you follow it. - Use diagrams to visualize the tree and the traversal process. - Practice with different types of trees to get comfortable with edge cases. ## Conclusion Inorder traversal is a fundamental tree traversal technique with various applications. Understanding both recursive and iterative approaches is crucial for solving related problems efficiently. Practice and familiarity with different tree structures will enhance problem-solving skills. ## Additional Resources - [Binary Tree Traversal](https://en.wikipedia.org/wiki/Tree_traversal) - [LeetCode - Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) - [GeeksforGeeks - Inorder Tree Traversal](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/) By mastering these concepts, you will be well-equipped to tackle a wide range of tree-related problems in coding interviews and real-world applications. Happy coding!