← All posts

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

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;
}