Binary Tree Inorder Traversal
LeetCode #94 · Easy · Trees · C++ solution with worked-out approach and complexity analysis.
Approach
Iterative Inorder Traversal using Stack
Use a stack to simulate the recursive call stack. Process nodes in left-root-right order by: 1. Push all left nodes onto the stack 2. Pop and process the current node 3. Move to the right subtree
Time
O(n)
visit each node exactly once
Space
O(h)
h is the height of the tree (stack space)
Problem description(from LeetCode)
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Examples
Example 1
- Input:
- root = [1,null,2,3]
- Output:
- [1,3,2]
Example 2
- Input:
- root = [1,2,3,4,5,null,8,null,null,6,7,9]
- Output:
- [4,2,6,5,7,1,3,9,8]
Example 3
- Input:
- root = []
- Output:
- []
Example 4
- Input:
- root = [1]
- Output:
- [1]
Constraints
- •The number of nodes in the tree is in the range [0, 100].
- •-100 <= Node.val <= 100
C++ Solution
solution.cpp
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:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode *> st;
TreeNode *curr = root;
while (curr != nullptr || !st.empty()) {
while (curr != nullptr) {
st.push(curr);
curr = curr->left;
}
curr = st.top();
st.pop();
res.push_back(curr->val);
curr = curr->right;
}
return res;
}
};