Implementing Binary Search Tree in JavaScript

// Create a BinarySearchTree
function BinarySerachTree() {
  // Create a node constructor function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  // Save the root property this.root = null

  // Binary search tree related operation methods // Insert data into the tree BinarySerachTree.prototype.insert = function (key) {
    // 1. Create the corresponding node according to the key
    var newNode = new Node(key)

    // 2. Determine whether the root node has a value if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }

  BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) { // 1. Prepare to insert data into the left subtree if (node.left === null) { // 1.1. There is no content in the left subtree of node node.left = newNode
      } else { // 1.2. The left subtree of node already has content this.insertNode(node.left, newNode)
      }
    } else { // 2. Prepare to insert data into the right subtree if (node.right === null) { // 2.1. There is no content in the right subtree of node node.right = newNode
      } else { // 2.2. There is content in the right subtree of node this.insertNode(node.right, newNode)
      }
    }
  }

  // Get the maximum and minimum values ​​BinarySerachTree.prototype.min = function () {
    var node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }

  BinarySerachTree.prototype.max = function () {
    var node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }

  //Search for a specific value/*
  BinarySerachTree.prototype.search = function (key) {
    return this.searchNode(this.root, key)
  }

  BinarySerachTree.prototype.searchNode = function (node, key) {
    // 1. If the passed node is null, then exit the recursion if (node ​​=== null) {
      return false
    }

    // 2. Determine the value of the node and the size of the passed key if (node.key > key) { // 2.1. The passed key is smaller, continue to search to the left return this.searchNode(node.left, key)
    } else if (node.key < key) { // 2.2. The key passed in is larger, continue searching to the right return this.searchNode(node.right, key)
    } else { // 2.3. Same, indicating the key is found
      return true
    }
  }
  */
  BinarySerachTree.prototype.search = function (key) {
    var node = this.root
    while (node ​​!== null) {
      if (node.key > key) {
        node = node.left
      } else if (node.key < key) {
        node = node.right
      } else {
        return true
      }
    }
    return false
  }

  // Delete nodeBinarySerachTree.prototype.remove = function (key) {
    // 1. Get the current node
    var node = this.root
    var parent = null

    // 2. Loop through the nodes
    while (node) {
      if (node.key > key) {
        parent = node
        node = node.left
      } else if (node.key < key) {
        parent = node
        node = node.right
      } else {
        if (node.left == null && node.right == null) {

        }
      }
    }
  }

  BinarySerachTree.prototype.removeNode = function (node, key) {
    // 1. If the passed node is null, exit the recursion directly.
    if (node ​​=== null) return null

    // 2. Determine the size of key and corresponding node.key if (node.key > key) {
      node.left = this.removeNode(node.left, key)

    }
  }

  // Delete node BinarySerachTree.prototype.remove = function (key) {
    // 1. Define temporary saved variables var current = this.root
    var parent = this.root
    var isLeftChild = true

    // 2. Start searching for nodes while (current.key !== key) {
      parent = current
      if (key < current.key) {
        isLeftChild = true
        current = current.left
      } else {
        isLeftChild = false
        current = current.right
      }

      // If you find that current already points to null, it means that the data to be deleted is not found if (current === null) return false
    }

    // 3. The deleted node is a leaf node if (current.left === null && current.right === null) {
      if (current == this.root) {
        this.root == null
      } else if (isLeftChild) {
        parent.left = null
      } else {
        parent.right = null
      }
    }

    // 4. Delete the node with one child node else if (current.right === null) {
      if (current == this.root) {
        this.root = current.left
      } else if (isLeftChild) {
        parent.left = current.left
      } else {
        parent.right = current.left
      }
    } else if (current.left === null) {
      if (current == this.root) {
        this.root = current.right
      } else if (isLeftChild) {
        parent.left = current.right
      } else {
        parent.right = current.right
      }
    }

    // 5. Delete the node with two nodes else {
      // 1. Get the successor node var successor = this.getSuccessor(current)

      // 2. Determine whether it is the root node if (current == this.root) {
        this.root = successor
      } else if (isLeftChild) {
        parent.left = successor
      } else {
        parent.right = successor
      }

      // 3. Assign the left subtree of the deleted node to successor
      successor.left = current.left
    }

    return true
  }

  // Find the successor methodBinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1. Use variables to save temporary nodes var successorParent = delNode
    var successor = delNode
    var current = delNode.right // Start from the right subtree // 2. Find the node while (current != null) {
      successorParent = successor
      successor = current
      current = current.left
    }

    // 3. If you want to delete 15 in the figure, you also need the following code if (successor != delNode.right) {
      successorParent.left = successor.right
      successor.right = delNode.right
    }
  }

  // Traversal method //handler is a callback function // Pre-order traversal BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if (node ​​!== null) {
      handler(node.key)
      this.preOrderTranversalNode(node.left, handler)
      this.preOrderTranversalNode(node.right, handler)
    }
  }

  // In-order traversalBinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node ​​!== null) {
      this.inOrderTraversalNode(node.left, handler)
      handler(node.key)
      this.inOrderTraversalNode(node.right, handler)
    }
  }

  // Subsequent traversalBinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node ​​!== null) {
      this.postOrderTraversalNode(node.left, handler)
      this.postOrderTraversalNode(node.right, handler)
      handler(node.key)
    }
  }
  
  /*
  // Test traversal results (inOrderTraversal can be replaced with other traversal methods)
    resultString = ""
    bst.inOrderTraversal(function (key) {
      resultString += key + " "
    })
    alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 
   */
}