ā All posts

# Data Structures / Binary Tree/In-order Traversal with Stack

Posted On 12.28.2021

This one is a bit more compex than the pre-order (in term of using stack).

Algorithm:

- Create an empty stack
- Create a temporary reference called curr, set it as root
- Repeat while curr still not null, or the stack still not empty
- For each tree starting from node curr, we want to push every left nodes in that tree to the stack. To do this, repeat while curr still has a left child, push its left node to the stack and set curr as its left.
- Start popping out the stack and set it as curr, visit that node and set curr to its right node.

Implementation:

```
let stack = [];
let curr = root;
while (curr !== null || stack.length) {
while (curr !== null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
curr.visit();
curr = curr.right;
}
```