Binary Search Tree

A Binary Search Tree is a binary tree where each node contains a key and an optional associated value.

It allows particularly fast lookup, addition, and removal of items.

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

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

  // Insert a value into the BST
  insert(value) {
    const newNode = new TreeNode(value);
    if (!this.root) {
      this.root = newNode;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (!node.left) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (!node.right) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }

  // Search for a value in the BST
  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    if (!node) return false;
    if (node.value === value) return true;
    if (value < node.value) {
      return this._searchNode(node.left, value);
    } else {
      return this._searchNode(node.right, value);
    }
  }

  // Remove a value from the BST
  remove(value) {
    this.root = this._removeNode(this.root, value);
  }

  _removeNode(node, value) {
    if (!node) return null;

    if (value < node.value) {
      node.left = this._removeNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._removeNode(node.right, value);
    } else {
      if (!node.left && !node.right) {
        return null;
      } else if (!node.left) {
        return node.right;
      } else if (!node.right) {
        return node.left;
      } else {
        const minRightNode = this._findMinNode(node.right);
        node.value = minRightNode.value;
        node.right = this._removeNode(node.right, minRightNode.value);
      }
    }

    return node;
  }

  _findMinNode(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  // Rotate the BST (for demonstration, a simple left rotation is implemented)
  rotate() {
    const newRoot = this.root.right;
    this.root.right = newRoot.left;
    newRoot.left = this.root;
    this.root = newRoot;
  }

  // Reverse the BST
  reverse() {
    this.root = this._reverseNode(this.root);
  }

  _reverseNode(node) {
    if (!node) return null;

    const left = this._reverseNode(node.left);
    const right = this._reverseNode(node.right);

    node.left = right;
    node.right = left;

    return node;
  }

  // Insert a value at a specific position in the BST
  insertAt(position, value) {
    // Convert BST to array, insert value, and then rebuild the tree
    const arr = this._inOrderTraversal(this.root, []);
    arr.splice(position, 0, value);
    this.root = this._buildBSTFromSortedArray(arr, 0, arr.length - 1);
  }

  _buildBSTFromSortedArray(arr, start, end) {
    if (start > end) return null;

    const mid = Math.floor((start + end) / 2);
    const newNode = new TreeNode(arr[mid]);

    newNode.left = this._buildBSTFromSortedArray(arr, start, mid - 1);
    newNode.right = this._buildBSTFromSortedArray(arr, mid + 1, end);

    return newNode;
  }

  // Remove a value at a specific position in the BST
  removeAt(position) {
    // Convert BST to array, remove value at position, and then rebuild the tree
    const arr = this._inOrderTraversal(this.root, []);
    arr.splice(position, 1);
    this.root = this._buildBSTFromSortedArray(arr, 0, arr.length - 1);
  }

  // Print the BST (in-order traversal)
  print() {
    console.log("BST:");
    this._inOrderPrint(this.root);
  }

  _inOrderPrint(node) {
    if (node) {
      this._inOrderPrint(node.left);
      console.log(node.value);
      this._inOrderPrint(node.right);
    }
  }

  // In-order traversal (returns an array of values)
  inOrderTraversal() {
    return this._inOrderTraversal(this.root, []);
  }

  _inOrderTraversal(node, result) {
    if (node) {
      this._inOrderTraversal(node.left, result);
      result.push(node.value);
      this._inOrderTraversal(node.right, result);
    }
    return result;
  }
}

// Example usage:
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.print(); // Print the BST
console.log("Search 7:", bst.search(7)); // Output: true
console.log("Search 20:", bst.search(20)); // Output: false

bst.remove(5); // Remove value 5
bst.print(); // Print the updated BST

bst.rotate(); // Rotate the BST
bst.print(); // Print the rotated BST

bst.reverse(); // Reverse the BST
bst.print(); // Print the reversed BST

bst.insertAt(2, 8); // Insert value 8 at position 2
bst.print(); // Print the updated BST

bst.removeAt(1); // Remove value at position 1
bst.print(); // Print the updated BST

The nodes are arranged in a binary search tree according to the following properties:

  1. The left subtree of a particular node will always contain nodes with keys less than that node’s key.

  2. The right subtree of a particular node will always contain nodes with keys greater than that node’s key.

  3. The left and the right subtree of a particular node will also, in turn, be binary search trees.

Time Complexity

In average cases, the above mentioned properties enable the insert, search and deletion operations in O(log n) time where n is the number of nodes in the tree.

However, the time complexity for these operations is O(n) in the worst case when the tree becomes unbalanced.

Space Complexity

The space complexity of a binary search tree is O(n) in both the average and the worst cases.

Balanced vs. Unbalanced BST

A binary tree is called balanced if every leaf node is not more than a certain distance away from the root than any other leaf.

That is, if we take any two leaf nodes (including empty nodes), the distance between each node and the root is approximately the same.

In most cases, "approximately the same" means that the difference between the two distances (root to first leaf and root to second leaf) is not greater than 1, but the exact number can vary from application to application.

This distance constraint ensures that it takes approximately the same amount of time to reach any leaf node in a binary tree from the root.

A linked list is a kind of maximally-unbalanced binary tree.

Binary Search Tree Good at 😀:

  • Better than O(n)

  • Ordered

  • Flexible Size

Binary Search Tree Bad at 😒:

  • No O(1) operations

Balancing a Binary Search Tree

The primary issue with binary search trees is that they can be unbalanced.

In the worst case, they are still not more efficient than a linked list, performing operations such as insertions, deletions, and searches in O(n) time.

FeatureBinary TreeBinary Search Tree (BST)

Structure

A hierarchical data structure with at most two children (left and right) for each node.

A specific type of binary tree where nodes are ordered according to a particular rule.

Node Insertion

Nodes can be inserted in any order without specific rules governing their arrangement.

Nodes are inserted in a way that maintains the ordering property of the BST.

Ordering Property

No specific ordering constraints on the values of nodes.

For every node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.

Search Efficiency

May not offer efficient search operations.

Offers efficient search operations (typically O(log n) on average).

Common Use Cases

Used for a variety of purposes, such as representing hierarchical data structures or organizing data for traversal operations.

Commonly used in scenarios where efficient searching is required, such as implementing dictionaries, sets, or databases.

PreviousBinary TreeNextAVL Tree

Last updated