« All posts

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

Read more