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:

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

• Example 2:

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

• Example 3:

1Input: root = [1]
2Output: [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

 1class Solution {
 2public:
 3    vector<int> inorderTraversal(TreeNode* root) {
 4        if (root == nullptr) return {};  // corner case: empty tree
 5        
 6        TreeNode * p = root;
 7        stack<TreeNode *> stk;
 8
 9        vector<int>  ans;
10        while (p != nullptr || stk.empty() == false) {
11            while (p != nullptr) {  // To Left Child, until end
12                stk.push(p);
13                p = p->left;
14            }
15            p = stk.top();  stk.pop();
16            ans.push_back(p->val);  // Node->val
17            p = p->right;           // Right Child
18        }
19
20        return ans;
21    }
22};

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) $