Binary Tree Inorder Traversal easy

Problem Statement

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: []

Steps

The inorder traversal of a binary tree follows this recursive pattern:

1. Traverse the left subtree recursively.
2. Visit the root node.
3. Traverse the right subtree recursively.

To implement this iteratively, we can use a stack to simulate the recursion.

Explanation

The iterative approach uses a stack to keep track of nodes to visit. We start by pushing the root node onto the stack. Then, we repeatedly pop a node from the stack. If the node has a left child, we push the left child and all its left descendants onto the stack (this ensures we process the left subtree completely before the root). After processing the left subtree (or if there's no left subtree), we visit the node (add its value to the result), and then push its right child (if it exists) onto the stack. This process continues until the stack is empty.

Code

#include <vector>
#include <stack>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    std::vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> s;
        TreeNode* curr = root;

        while (curr != nullptr || !s.empty()) {
            while (curr != nullptr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }

        return result;
    }
};

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(H), where H is the height of the tree. In the worst case (a skewed tree), the space complexity can be O(N), but in a balanced tree, it would be O(log N). This is due to the space used by the stack, which can hold at most H nodes.