[JS] 이진 트리 순회

1. Node Class

class BinaryTreeNode {
  constructor(val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }
}

2. 선순위 순회

function traversePreOreder(node, callbackFunc) {
  callbackFunc(node.value);
  if (node.left) traversePreOreder(node.left, callbackFunc);
  if (node.right) traversePreOreder(node.right, callbackFunc);
}

재귀를 사용하지 않는 방법

function traversePreOrederIterative(node, callbackFunc) {
  const nodeStack = [node];

  while (nodeStack.length) {
    const cur = nodeStack.pop();
    callbackFunc(cur.value);

    if (cur.right) nodeStack.push(cur.right);
    if (cur.left) nodeStack.push(cur.left);
  }
}

2. 중순위 순회

function traverseInOrder(node, callbackFunc) {
  if (node.left) traverseInOrder(node.left, callbackFunc);
  callbackFunc(node.value);
  if (node.right) traverseInOrder(node.right, callbackFunc);
}

재귀를 사용하지 않는 방법

function traverseInOrderOterative(node, callbackFunc) {
  const stack = [];
  let cur = node;

  while (true) {
    if (cur !== null) {
      stack.push(cur);
      cur = cur.left;
      continue;
    }
    
    if (stack.length) {
      cur = stack.pop();
      callbackFunc(cur.value);
      cur = cur.right;
      continue;
    }

    break;
  }
}

3. 후순위 순회

function traversePostOrder(node, callbackFunc) {
  if (node.left) traversePostOrder(node.left, callbackFunc);
  if (node.right) traversePostOrder(node.right, callbackFunc);
  callbackFunc(node.value);
}

재귀를 사용하지 않는 방법

function traversePostOrderIterative(node, callbackFunc) {
  const stack1 = [node];
  const stack2 = [];

  while (stack1.length) {
    const cur = stack1.pop();
    stack2.push(cur.value);

    if (cur.left) stack1.push(cur.left);
    if (cur.right) stack1.push(cur.right);
  }


  for (let i = stack2.length - 1; i >= 0; i -= 1) {
    callbackFunc(stack2[i]);
  }
}