Iterative Inorder Traversal
Do the inorder traversal (Left, Root, Right) of a binary tree without recursion. Return the node values as a list.
This is the iterative version of Binary Tree Inorder Traversal (LeetCode 94), and the basis for the BST Iterator problem later in this track.
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6Inorder cannot visit a node until its entire left subtree is done. So from any node we first walk as far left as we can, remembering the path on a stack. The node on top of the stack is then the leftmost unvisited node, which is exactly the next one to record.
After recording it, the next candidate is its right subtree, and we repeat the same "go left as far as possible" idea there.
Approach: Walk Left, Pop, Go Right
Keep a pointer node, starting at the root, and a stack.
- While
nodeis not null, push it and move tonode.left. This pushes the whole left spine. - When
nodebecomes null, the stack top is the next node in inorder. Pop it and add its value. - Move to its right child and repeat from step 1.
- Stop when
nodeis null and the stack is empty.
Dry run on the sample tree:
- Go left: push 1, push 2, push 4. Stack
[1, 2, 4]. - Pop 4, answer
[4]. Its right is null. - Pop 2, answer
[4, 2]. Go right to 5, push it. Pop 5, answer[4, 2, 5]. - Pop 1, answer
[4, 2, 5, 1]. Go right to 3, push it. Pop 3, answer[4, 2, 5, 1, 3]. - Go right to 6, push it. Pop 6, answer
[4, 2, 5, 1, 3, 6].
Code
class Solution {public:vector<int> inorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*> st;TreeNode* node = root;while (node != nullptr || !st.empty()) {while (node != nullptr) {st.push(node);node = node->left;}node = st.top();st.pop();ans.push_back(node->val);node = node->right;}return ans;}};
Complexity
Each node is pushed once and popped once.
The stack holds the current left spine, at most the tree height. O(n) for a skewed tree.