SHARE
TWEET

Untitled

a guest Aug 17th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // class for node
  2. class Node{
  3.   constructor(value){
  4.     this.value = value
  5.     this.left = null
  6.     this.right = null
  7.   }
  8. }
  9.  
  10. // BST
  11.  
  12. class BST{
  13.   constructor(value){
  14.     this.root = new Node(value)
  15.     this.count =0
  16.   }
  17.  
  18.   // insert
  19.   insert (value) {
  20.     this.count++
  21.     const newNode = new Node(value)
  22.     const searchTree = (node) =>{
  23.       //If value is less then node value go left
  24.       if(value < node.value){
  25.         if(!node.left){
  26.           node.left = newNode
  27.         }else
  28.         {
  29.           searchTree(node.left)
  30.         }
  31.       }
  32.       //If value is greater then node value go right
  33.       else if(value > node.value){
  34.         if(!node.right){
  35.           node.right = newNode
  36.         }else
  37.         {
  38.           searchTree(node.right)
  39.         }
  40.       }
  41.     }
  42.     searchTree(this.root)
  43.   }
  44.  
  45.   //min
  46.   min(){
  47.     let currentNode = this.root
  48.     while(currentNode.left){
  49.       currentNode = currentNode.left
  50.     }
  51.     return currentNode.value
  52.   }
  53.  
  54.   //max
  55.   max(){
  56.     let currentNode = this.root
  57.     while(currentNode.right){
  58.       currentNode = currentNode.right
  59.     }
  60.     return currentNode.value
  61.   }
  62.  
  63.   // contains
  64.   contains(value){
  65.     let currentNode = this.root
  66.    
  67.     while(currentNode){
  68.       if(value === currentNode.value){
  69.         return true;
  70.       }
  71.       if(value < currentNode.value){
  72.         currentNode = currentNode.left
  73.       }else{
  74.         currentNode = currentNode.right
  75.       }
  76.     }
  77.     return false
  78.   }
  79.  
  80.   // left root right
  81.   dfsInOrder(){
  82.     let result =[]
  83.     const traverse = node =>{
  84.       if(node.left) traverse(node.left);
  85.       result.push(node.value)
  86.       if(node.right) traverse(node.right);
  87.     }
  88.     traverse(this.root)
  89.     return result
  90.   }
  91.  
  92.   //root left right
  93.   dfsPreOrder(){
  94.     let result =[]
  95.     const traverse = node =>{
  96.       result.push(node.value)
  97.       if(node.left) traverse(node.left);
  98.       if(node.right) traverse(node.right);
  99.     }
  100.     traverse(this.root)
  101.     return result
  102.   }
  103.  
  104.   //left right root
  105.   dfsPostOrder(){
  106.     let result =[]
  107.     const traverse = node =>{
  108.       if(node.left) traverse(node.left);
  109.       if(node.right) traverse(node.right);
  110.       result.push(node.value)
  111.     }
  112.     traverse(this.root)
  113.     return result
  114.   }
  115.  
  116.   //bfs
  117.   bfs(){
  118.     let result =[]
  119.     let queue = []
  120.    
  121.     while(queue.length){
  122.       let currentNode = queue.unshift()
  123.       result.push(currentNode.value)
  124.       if(currentNode.left){
  125.         queue.push(currentNode.left)
  126.       }
  127.       if(currentNode.right){
  128.         queue.push(currentNode.right)
  129.       }
  130.     }
  131.     return result
  132.   }
  133. }
  134.  
  135. const myBST = new BST(8)
  136. myBST.insert(3)
  137. myBST.insert(10)
  138. myBST.insert(1)
  139. myBST.insert(6)
  140. myBST.insert(14)
  141. myBST.insert(13)
  142. myBST.contains(13)
  143. myBST.contains(23)
  144. myBST.dfsInOrder()
  145. console.log(myBST)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top