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

## Understanding the Problem Inorder traversal of a binary tree involves visiting the nodes in the following order: 1. Visit the left subtree. 2. Visit the root node. 3. Visit the right subtree. ### Core Challenge The main challenge is to correctly implement the inorder traversal, especially iteratively, as the recursive solution is straightforward but may not be optimal for large trees due to stack overflow risks. ### Significance and Applications Inorder traversal is significant in scenarios where the nodes need to be processed in a sorted order, such as in binary search trees (BSTs). ### Potential Pitfalls - Misunderstanding the traversal order. - Incorrectly handling null nodes. - Stack overflow in recursive solutions for large trees. ## Approach ### Naive Solution: Recursive Approach The recursive approach is simple and intuitive: 1. Recursively traverse the left subtree. 2. Process the current node. 3. Recursively traverse the right subtree. #### Limitations - Stack overflow for deep trees. - Not suitable for environments with limited stack size. ### Optimized Solution: Iterative Approach To avoid the limitations of recursion, we can use an iterative approach with an explicit stack: 1. Use a stack to simulate the recursive call stack. 2. Traverse the tree iteratively, pushing nodes onto the stack and processing them in the correct order. ### Thought Process 1. Initialize an empty stack and a pointer to the root node. 2. Traverse to the leftmost node, pushing all nodes onto the stack. 3. Pop nodes from the stack, process them, and move to the right subtree. ## Algorithm ### Recursive Algorithm 1. Define a helper function to perform the inorder traversal. 2. Base case: if the node is null, return. 3. Recursively traverse the left subtree. 4. Process the current node. 5. Recursively traverse the right subtree. ### Iterative Algorithm 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: - Traverse to the leftmost node, pushing nodes onto the stack. - Pop a node from the stack, process it, and move to its right subtree. ## Code Implementation ### Recursive Solution

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    void inorderTraversalHelper(TreeNode* root, vector& result) {
        if (root == nullptr) return;
        inorderTraversalHelper(root->left, result); // Traverse left subtree
        result.push_back(root->val); // Process current node
        inorderTraversalHelper(root->right, result); // Traverse right subtree
    }

    vector inorderTraversal(TreeNode* root) {
        vector result;
        inorderTraversalHelper(root, result);
        return result;
    }
};

### Iterative Solution

#include <vector>
#include <stack>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack stk;
        TreeNode* current = root;

        while (current != nullptr || !stk.empty()) {
            // Reach the leftmost node of the current node
            while (current != nullptr) {
                stk.push(current);
                current = current->left;
            }
            // Current must be nullptr at this point
            current = stk.top();
            stk.pop();
            result.push_back(current->val); // Process 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 Solution - **Time Complexity**: O(n), where n is the number of nodes in the tree. - **Space Complexity**: O(h), where h is the height of the tree (due to the call stack). ### Iterative Solution - **Time Complexity**: O(n), where n is the number of nodes in the tree. - **Space Complexity**: O(h), where h is 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 on one side (e.g., a linked list). ### Example Edge Cases 1. **Empty Tree**: - **Input**: `[]` - **Output**: `[]` 2. **Single Node**: - **Input**: `[1]` - **Output**: `[1]` 3. **Linked List (All Right Nodes)**: - **Input**: `[1, null, 2, null, 3]` - **Output**: `[1, 2, 3]` ## Testing ### Comprehensive Testing - Test with a variety of tree structures. - Include edge cases and large trees. - Use testing frameworks like Google Test for automated testing. ### Example Test Cases 1. Balanced tree. 2. Unbalanced tree. 3. Trees with varying depths. ## Thinking and Problem-Solving Tips - Break down the problem into smaller parts. - Visualize the tree and the traversal process. - Practice with different tree structures to understand the traversal order. ## Conclusion Understanding and implementing binary tree traversals is fundamental in computer science. The iterative approach to inorder traversal is efficient and avoids the pitfalls of recursion. Practice and familiarity with different tree structures will enhance problem-solving skills. ## Additional Resources - [Binary Tree Traversal Techniques](https://en.wikipedia.org/wiki/Tree_traversal) - [LeetCode Problems on Tree Traversals](https://leetcode.com/tag/tree/) - [GeeksforGeeks Tree Traversal](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/) By mastering these concepts, you will be well-equipped to handle a wide range of tree-related problems in coding interviews and real-world applications.