BFS and DFS trees
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
class Node {
constructor(value)
{
this.left = null;
this.data = value;
this.right = null;
}
}
class BinarySearchTree{
constructor()
{
this.root = null
}
insert(value)
{
let newNode = new Node(value);
if(!this.root) this.root = newNode;
else {
let curr = this.root;
while(1)
{
if(value<curr.data){
if(!curr.left) {curr.left = newNode; break;}
else
curr = curr.left;
}
else {
if(!curr.right) {curr.right = newNode; break;}
else
curr = curr.right;
}
}
}
}
inorder()
{
let arr = [];
inorder_trav(this.root,arr);
console.log(arr);
}
postorder()
{
let arr = [];
postorder_trav(this.root,arr);
console.log(arr);
}
preorder()
{
let arr = [];
preorder_trav(this.root,arr);
console.log(arr);
}
breadthFirstSearch()
{
let queue = [this.root];
let list = [];
while(queue.length!=0)
{
let currNode = queue.shift();
list.push(currNode.data);
if(currNode.left)
queue.push(currNode.left);
if(currNode.right)
queue.push(currNode.right);
}
console.log(list);
}
breadthFirstSearchR(queue,list)
{
if(!queue.length) return list;
let node = queue.shift();
list.push(node.data);
if(node.left)
queue.push(node.left);
if(node.right)
queue.push(node.right);
return this.breadthFirstSearchR(queue,list);
}
}
const inorder_trav = (root,arr)=>{
if(!root) return;
inorder_trav(root.left,arr)
arr.push(root.data);
inorder_trav(root.right,arr);
}
const postorder_trav = (root,arr)=>{
if(!root) return;
postorder_trav(root.left,arr);
postorder_trav(root.right,arr);
arr.push(root.data);
}
const preorder_trav = (root,arr)=>{
if(!root) return;
arr.push(root.data);
preorder_trav(root.left,arr);
preorder_trav(root.right,arr);
}
let obj = new BinarySearchTree();
obj.insert(9);
obj.insert(4);
obj.insert(6);
obj.insert(20);
obj.insert(170);
obj.insert(15);
obj.insert(1);
obj.inorder();
// obj.breadthFirstSearch();
obj.postorder();
obj.preorder();
// console.log(obj.breadthFirstSearchR([obj.root],[]));
JavaScript
INFO