Inorder traversal of binary tree, from recursive to iterative

in-order.js

const tree = {
  value: 'A',
  left: {
    value: 'B',
    left: {
      value: 'D',
      left: {
        value: 'H',
      },
      right: {
        value: 'I'
      },
    },
    right: {
      value: 'E',
      left: {
        value: 'J'
      },
    },
  },
  right: {
    value: 'C',
    left: {
      value: 'F',
    },
    right: {
      value: 'G',
    },
  },
};

// recursive
function inOrderTraverse1(root) {
  if (!root) {
    return;
  }
  inOrderTraverse1(root.left);
  console.log(root.value);
  inOrderTraverse1(root.right);
}

// call = push stack variables and return address to stack, setup stack variables according to function parameter, then goto beginning
// return = pop stack variables from stack, reset stack variables and execution address from stack content, then and go to beginning
// given that we only have `root` as stack variable, the stack is just an array of roots
function inOrderTraverse2(root) {
  const stack = [];
  let pc = 0;
  while (true) {
    switch (pc) {
      case 0: {
        if (!root) {
          // return, i.e. pop stack
          if (stack.length === 0) {
            return;
          }
          ({ root, pc } = stack.pop());
          continue;
        }
        // inOrderTraverse1(root.left);
        stack.push({ root, pc: 1 });
        root = root.left;
        pc = 0;
        continue;
      }
      case 1: {
        console.log(root.value);
        // inOrderTraverse1(root.right);
        stack.push({ root, pc: 2 });
        root = root.right;
        pc = 0;
        continue;
      }
      case 2: {
        // return, i.e. pop stack
        if (stack.length === 0) {
          return;
        }
        ({ root, pc } = stack.pop());
        continue;
      }
    }
  }
}