Sure. Your tree is:
1
/ \
2 3
/ \ \
4 5 6
We want inorder = Left → Root → Right.
Let's dry-run the iterative code.
Initial state
current = root; // 1
stack = []
result = []
Step 1 — Go left
while (current) {
stk.push(current);
current = current->left;
}
Push 1:
stack = [1]
current = 2
Push 2:
stack = [1, 2]
current = 4
Push 4:
stack = [1, 2, 4]
current = nullptr
Now we stop because there is no more left child.
Step 2 — Process 4
current = stk.top(); // 4
stk.pop();
result.push_back(current->val);
Now:
stack = [1, 2]
result = [4]
Then:
current = current->right;
4 has no right child:
current = nullptr
Step 3 — Process 2
Inner while doesn't run because current == nullptr.
current = stk.top(); // 2
stk.pop();
result.push_back(2);
Now:
stack = [1]
result = [4, 2]
Then:
current = current->right;
2's right child is 5:
current = 5
Step 4 — Process 5
Push 5:
stack = [1, 5]
current = nullptr
Process 5:
result = [4, 2, 5]
stack = [1]
5 has no right child:
current = nullptr
Step 5 — Process 1
Take from stack:
current = 1
stack = []
result = [4, 2, 5, 1]
Then:
current = current->right;
1's right child is 3:
current = 3
Step 6 — Go to 3's right side
3 has no left child, so process 3:
result = [4, 2, 5, 1, 3]
Then:
current = current->right;
3's right child is 6.
current = 6
Process 6:
result = [4, 2, 5, 1, 3, 6]
6 has no children, so:
current = nullptr
stack = []
Now the outer condition:
while (current || !stk.empty())
becomes:
while (false || false)
So the loop ends.
Final answer
[4, 2, 5, 1, 3, 6]
The key thing to notice is that the stack lets us pause nodes like 1 and 2 while we go deeper into their left children.
Top comments (0)