Breadth First Search (Binary Search Tree에서)

너비 우선 탐색과 깊이 우선 탐색 비교

출처 https://velog.io/@nomadhash/Algorithm-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-Breadth-First-Search

코딩

var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
// Only change code below this line

function traverse(direction, root) {
//queue에 루트를 넣고
const queue = [root];
const results = [];

function pushIfThere(node) {
  //node가 null이 아니라면 queue에 넣음
  if (node) queue.push(node);
}//pushIfThere


while (queue.length > 0) {
  
  const node = queue.shift();
  results.push(node.value);
  if (direction === "level") {
    // Level order: left to right
    pushIfThere(node.left);
    pushIfThere(node.right);
  } else {
    // Reverse level order: right to left
    pushIfThere(node.right);
    pushIfThere(node.left);
  }
}//while

return results;

}//traverse

// Level order traversal
this.levelOrder = function() {
if (!this.root) return null;

return traverse("level", this.root);

}

// Reverse level order traversal
this.reverseLevelOrder = function() {
if (!this.root) return null;

return traverse("reverseLevel", this.root);

}
// Only change code above this line
}