Binary Search Tree

Implement a binary search tree (BST) data structure that supports the following operations:

new BST(): Creates an instance of a BST class. It initializes the root to null as there are no nodes in the tree initially.
insert(value): Adds a new value to the BST. The new value is inserted in the correct position to maintain the binary search tree order. If the tree is empty, the new value becomes the root. Required time complexity: O(log n) on average, but can degrade to O(n) in the worst case where the tree becomes a linear chain.
search(value): Searches for a value in the BST. Returns true if the value exists in the tree; otherwise, returns false. This operation also adheres to the average time complexity of O(log n) but can become O(n) in the worst case.
delete(value): Removes a value from the BST, if it exists. This method requires handling three cases: deleting a node with no children, one child, or two children. The function maintains the properties of the BST after deletion. Required time complexity: O(log n) on average, but may be O(n) in the worst case.

Examples

const bst = new BST();
bst.insert(15);
bst.insert(10);
bst.insert(20);
bst.search(10); // true
bst.delete(10);
bst.search(10); // false

Solution

Binary Search Trees (BSTs) are a fundamental data structure in computer science, primarily used to maintain a dynamically changing dataset in a sorted order. Each node in a BST contains a key and pointers to its left and right children. The tree is structured such that for any given node, all nodes in its left subtree have keys less than the node’s key, and all nodes in its right subtree have keys greater than the node’s key. This property enables efficient searching, insertion, and deletion operations.

class Node {
  constructor(value = null) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

export default class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  /**
   * Inserts a new value into the BST while maintaining BST properties.
   * @param {*} value The value to be inserted into the BST.
   */
  insert(value) {
    const newNode = new Node(value);
    if (this.root === null) {
      this.root = newNode;
      return;
    }

    let currentNode = this.root;
    let parent = null;
    while (currentNode) {
      parent = currentNode;
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else {
        currentNode = currentNode.right;
      }
    }

    if (value < parent.value) {
      parent.left = newNode;
    } else {
      parent.right = newNode;
    }
  }

  /**
   * Searches for a value in the BST. Returns true if the value exists, false otherwise.
   * @param {*} value The value to search for.
   * @return {boolean} True if the value is found, false otherwise.
   */
  search(value) {
    let currentNode = this.root;
    while (currentNode) {
      if (value === currentNode.value) {
        return true;
      }
      currentNode =
        value < currentNode.value ? currentNode.left : currentNode.right;
    }
    return false;
  }

  /**
   * Deletes a value from the BST, if it exists, while maintaining BST properties.
   * @param {*} value The value to be deleted from the BST.
   */
  delete(value) {
    let currentNode = this.root;
    let parent = null;

    // Find the node and its parent.
    while (currentNode && currentNode.value !== value) {
      parent = currentNode;
      if (value < currentNode.value) {
        currentNode = currentNode.left;
      } else {
        currentNode = currentNode.right;
      }
    }

    if (!currentNode) {
      return; // Node not found.
    }

    // Node has two children.
    if (currentNode.left && currentNode.right) {
      let successor = currentNode.right;
      let successorParent = currentNode;

      // Find the node with the smallest value in the right subtree and take note of its parent.
      while (successor.left) {
        successorParent = successor;
        successor = successor.left;
      }

      currentNode.value = successor.value; // Replace value.
      currentNode = successor; // Move pointer to successor, which will be deleted.
      parent = successorParent;
    }

    // Node has one or zero children.
    let child = currentNode.left ? currentNode.left : currentNode.right;

    // If the node to be deleted is the root node.
    if (!parent) {
      this.root = child;
    } else {
      if (parent.left === currentNode) {
        parent.left = child;
      } else {
        parent.right = child;
      }
    }
  }
}

Operations

new BST(): Initializes a new instance of a BST. The constructor sets the root of the tree to null, indicating that the tree is initially empty.
insert(value): Adds a new node with the given value to the BST. If the tree is empty, the new node becomes the root. If not, the tree is traversed starting from the root to find the correct position for the new node to maintain the BST property. This operation involves comparing the new value with the current node’s value and deciding to move left or right. The average time complexity is O(log n), but it can degrade to O(n) if values are inserted in an ascending/descending order.

search(value): Searches for a node containing the specified value. Starting from the root, the tree is traversed to the left or right depending on how the target value compares to the current node’s value. The process is repeated until the value is found or until a leaf is reached. Similar to insert(value), the average time complexity is O(log n), with a worst-case of O(n).
delete(value): Removes a node with the specified value from the BST. This operation is more complex as it needs to handle three cases:
- Leaf Node: Directly remove the node.
- Node with One Child: Remove the node and replace it with its child.
- Node with Two Children: Replace the node's value with the smallest value in the right subtree and then delete the successor node.

The deletion process ensures that the BST properties are maintained after the node is removed. Similar to insertion, the time complexity averages O(log n) but can become O(n).

Edge Cases

Inserting a value that already exists in the tree.
Deleting a node from an empty tree or a non-existent value.
Searching for a value not present in the tree.
Deleting duplicate values in the binary search tree.

Techniques

In-Order Traversal: Utilized during the delete operation to find the successor.
Object-Oriented Design: Using a Node class to represent each tree node and a BST class for the tree operations provides a clear structure and encapsulation.

This binary search tree implementation uses iterative solution, whereas a recursive solution for delete(value) may be easier to implement.

Binary Search Tree

Examples

Binary Search Tree

Examples

Similar questions

Solution

Operations

Edge Cases

Techniques

You must be signed in to view your submissions

Loading editor

Loading editor

Loading tests

JavaScript Console

Loading tests