Hi there, let’s talk about how to nonrecursively do a In-Order traversal for a Binary Tree.

A Binary Tree consists of 3 parts: the node itself, pointer to the left child, pointer to the right child.

An In-Order Traversal is to access the leftmost child firstly, then the node itself, and finally the right child.

1. Question

94. Binary Tree Inorder Traversal:

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

1.1 Examples

• Example 1:

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

• Example 2:

Input: root = []
Output: []

• Example 3:

Input: root = [1]
Output: [1]

1.2 Constraints

• The number of nodes in the tree is in the range $\left[ 0, 100 \right ]$.
• $-100 \leq \text{node.val} \leq 100$

2. Solution

To solve this problem, we will use stack.

This approach is a nonrecursive method.

2.1 Code

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if (root == nullptr) return {};  // corner case: empty tree

        TreeNode * p = root;
        stack<TreeNode *> stk;

        vector<int>  ans;
        while (p != nullptr || stk.empty() == false) {
            while (p != nullptr) {  // To Left Child, until end
                stk.push(p);
                p = p->left;
            }
            p = stk.top();  stk.pop();
            ans.push_back(p->val);  // Node->val
            p = p->right;           // Right Child
        }

        return ans;
    }
};

2.2 Complexity Analysis

Assume the number of nodes in the tree is $n$, and thus:

• Time complexity: $T(n) = O(n)$

• Space complexity: $S(n) = O(n)$