Inorder Traversal of Binary Tree

Harsh Yadav — Sun, 23 Aug 2026 15:26:27 +0000

Sure. Your tree is:

We want inorder = Left → Root → Right.

Let's dry-run the iterative code.

current = root;   // 1
stack = []
result = []

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.

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

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

Push 5:

stack = [1, 5]
current = nullptr

Process 5:

result = [4, 2, 5]
stack = [1]

5 has no right child:

current = nullptr

Take from stack:

current = 1
stack = []
result = [4, 2, 5, 1]

Then:

current = current->right;

1's right child is 3:

current = 3

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.

[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.

DEV Community: Harsh Yadav