Binary Tree Inorder Traversal in Java (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 gives the infix expression. ### Potential Pitfalls - Misunderstanding the order of traversal. - Handling null nodes and edge cases like an empty tree. ## Approach ### Naive Solution: Recursive Inorder Traversal The recursive approach is simple and intuitive: 1. Traverse the left subtree. 2. Visit the root node. 3. Traverse the right subtree. However, the recursive approach uses the call stack, which can lead to stack overflow for very deep trees. ### Optimized Solution: Iterative Inorder Traversal To avoid the limitations of recursion, we can use an iterative approach with a stack: 1. Use a stack to simulate the call stack of the recursive approach. 2. Push nodes to the stack until reaching the leftmost node. 3. Pop nodes from the stack, visit them, and then push the right subtree. ### Thought Process - Use a stack to keep track of nodes. - Push all left children to the stack. - Pop from the stack, visit the node, and push the right child. ## Algorithm ### Recursive Inorder Traversal 1. If the current node is null, return. 2. Recursively traverse the left subtree. 3. Visit the current node. 4. Recursively traverse the right subtree. ### Iterative Inorder Traversal 1. Initialize an empty stack and set the current node to the root. 2. While the current node is not null or the stack is not empty: - Push the current node to the stack and move to its left child. - If the current node is null, pop from the stack, visit the node, and move to its right child. ## Code Implementation ### Recursive Solution

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private void inorderHelper(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        // Traverse left subtree
        inorderHelper(node.left, result);
        // Visit node
        result.add(node.val);
        // Traverse right subtree
        inorderHelper(node.right, result);
    }
}

### Iterative Solution

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;

        while (current != null || !stack.isEmpty()) {
            // 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.add(current.val);
            // Visit the right subtree
            current = current.right;
        }
        return result;
    }
}

## Complexity Analysis ### Recursive Solution - **Time Complexity**: O(n), where n is the number of nodes. Each node is visited once. - **Space Complexity**: O(h), where h is the height of the tree. This is due to the recursion stack. ### Iterative Solution - **Time Complexity**: O(n), where n is the number of nodes. Each node is visited once. - **Space Complexity**: O(n), in the worst case, the stack will store all nodes in the tree. ## Edge Cases - **Empty Tree**: The output should be an empty list. - **Single Node Tree**: The output should be a list with one element. - **Skewed Tree**: The tree is skewed to the left or right, testing the stack's handling of such cases. ## Testing To test the solution comprehensively: - Test with an empty tree. - Test with a single node. - Test with a balanced tree. - Test with a skewed tree (left and right). ## Thinking and Problem-Solving Tips - Understand the traversal order and practice with different tree structures. - Use diagrams to visualize the stack operations in the iterative approach. - Practice converting recursive solutions to iterative ones using a stack. ## 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. ## Additional Resources - [Binary Tree Traversal](https://en.wikipedia.org/wiki/Tree_traversal) - [LeetCode Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/) - [GeeksforGeeks Inorder Traversal](https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/) By mastering these techniques, you can tackle a wide range of tree-related problems with confidence. Happy coding!