SHARE
TWEET

Untitled

a guest Apr 21st, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Node {
  2.   constructor(data) {
  3.     this.left = null
  4.     this.right = null
  5.     this.value = value
  6.   }
  7. }
  8.  
  9. class BST {
  10.   constructor() {
  11.     this.root = null
  12.   }
  13.  
  14.   // Insert a value as a node in the BST
  15.   insert(value) {
  16.     let newNode = new Node(value)
  17.    
  18.     // If root empty, set new node as the root
  19.     if (!this.root) {
  20.       this.root = newNode
  21.     } else {
  22.       this.insertNode(this.root, newNode)
  23.     }
  24.   }
  25.  
  26.   // helper function
  27.   insertNode(root, newNode) {
  28.     if (newNode.value < root.value) {
  29.       // If no left child, then just insesrt to the left
  30.       if (!root.left) {
  31.         root.left = newNode
  32.       } else {
  33.         this.insertNode(root.left, newNode)
  34.       }
  35.     } else {
  36.       // If no right child, then just insesrt to the right
  37.       if (!root.right) {
  38.         root.right = newNode
  39.       } else {
  40.         this.insertNode(root.right, newNode)
  41.       }
  42.     }
  43.   }
  44.  
  45.   // Remove a node with the value passed
  46.   remove(value) {
  47.     if (!this.root) {
  48.       return 'Tree is empty!'
  49.     } else {
  50.       this.removeNode(this.root, value)
  51.     }
  52.   }
  53.  
  54.   // helper function
  55.   removeNode(root, value) {
  56.     if (!root) {
  57.       return null
  58.     }
  59.    
  60.     // If value is less than root value, go to the left subtree
  61.     if (value < root.value) {
  62.       root.left = this.removeNode(root.left, value)
  63.       return root
  64.     // If value is greater than root value, go to the right subtree
  65.     } else if (value > root.value) {
  66.       root.right = tis.removeNode(root.right, value)
  67.       return root
  68.     // If we found the value, remove the node
  69.     } else {
  70.       // If no child nodes, just remove the node
  71.       if (!root.left && !root.right) {
  72.         root = null
  73.         return root
  74.       }
  75.      
  76.       // If one child (left)
  77.       if (root.left) {
  78.         root = root.left
  79.         return root
  80.       // If one child (right)
  81.       } else if (root.right) {
  82.         root = root.right
  83.         return root
  84.       }
  85.      
  86.       // If two child nodes (both)
  87.       // Get the minimum of the right subtree to ensure we have valid replacement
  88.       let minRight = this.findMinNode(root.right)
  89.       root.value = minRight.value
  90.      
  91.       // Make sure we remove the node that we replaced the deleted node
  92.       root.right = this.removeNode(root.right, minRight.value)
  93.       return root
  94.     }
  95.   }
  96.  
  97.   findMinNode(root) {
  98.     if (!root.left) {
  99.       return root
  100.     } else {
  101.       return this.findMinNode(root.left)
  102.     }
  103.   }
  104.  
  105.   // Return boolean value depending on the existence of the value in the tree
  106.   search(value) {
  107.     if (!this.root) {
  108.       return 'Tree is empty'
  109.     } else {
  110.       return Boolean(this.searchNode(this.root, value))
  111.     }
  112.   }
  113.  
  114.   searchNode(root, value) {
  115.     if (!root) {
  116.       return null
  117.     }
  118.    
  119.     if (value < root.value) {
  120.       return this.searchNode(root.left, value)
  121.     } else if (value > root.value) {
  122.       return this.searchNode(root.right, value)
  123.     }
  124.    
  125.     return root
  126.   }
  127. }
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
 
Top