Binary Search Tree

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree where each node has a key greater than all keys in its left subtree and smaller than all keys in its right subtree. This property makes BSTs useful for searching, inserting, and deleting elements efficiently.

Properties

1. Binary Tree: Each node has at most two children.
2. Ordered: For any node with a key K:
   • All keys in the left subtree are less than K.
   • All keys in the right subtree are greater than K.

Operations

1. Insertion: Adds a new node to the BST while maintaining the BST property.
2. Search: Finds a node with a specific key.
3. Deletion: Removes a node while maintaining the BST property.
4. Traversal: Visits all nodes in a specific order. Common traversals include:
   • In-Order: Left, Root, Right
   • Pre-Order: Root, Left, Right
   • Post-Order: Left, Right, Root

Time Complexity

• Insertion: O(log n) on average, O(n) in the worst case (when the tree is unbalanced)
• Search: O(log n) on average, O(n) in the worst case
• Deletion: O(log n) on average, O(n) in the worst case
• Traversal: O(n)

Example

Here’s a basic implementation of a Binary Search Tree in JavaScript:

// Define a class for a TreeNode, representing each node in the binary search tree
class TreeNode {
  constructor(key) {
    this.key = key;       // The value of the node
    this.left = null;     // Reference to the left child node
    this.right = null;    // Reference to the right child node
  }
}

// Define a class for the Binary Search Tree
class BinarySearchTree {
  constructor() {
    this.root = null; // The root of the tree, initially empty
  }

  // Method to insert a new key into the BST
  insert(key) {
    if (this.root === null) {
      // If the tree is empty, create the root node
      this.root = new TreeNode(key);
    } else {
      // Otherwise, insert the key in the correct position recursively
      this.insertRec(this.root, key);
    }
  }

  // Recursive method to insert a new key into the BST
  insertRec(node, key) {
    if (key < node.key) {
      // If the key is less than the current node's key, go to the left subtree
      if (node.left === null) {
        // If the left child is null, create a new node
        node.left = new TreeNode(key);
      } else {
        // Otherwise, recursively insert in the left subtree
        this.insertRec(node.left, key);
      }
    } else {
      // If the key is greater than or equal to the current node's key, go to the right subtree
      if (node.right === null) {
        // If the right child is null, create a new node
        node.right = new TreeNode(key);
      } else {
        // Otherwise, recursively insert in the right subtree
        this.insertRec(node.right, key);
      }
    }
  }

  // Method to search for a key in the BST
  search(key) {
    return this.searchRec(this.root, key);
  }

  // Recursive method to search for a key in the BST
  searchRec(node, key) {
    if (node === null || node.key === key) {
      // If the node is null or the key is found, return the node
      return node;
    }
    if (key < node.key) {
      // If the key is less than the current node's key, search in the left subtree
      return this.searchRec(node.left, key);
    }
    // If the key is greater than the current node's key, search in the right subtree
    return this.searchRec(node.right, key);
  }

  // Method to perform an in-order traversal of the BST
  inorderTraversal(node, result = []) {
    if (node !== null) {
      // Traverse the left subtree
      this.inorderTraversal(node.left, result);
      // Visit the current node
      result.push(node.key);
      // Traverse the right subtree
      this.inorderTraversal(node.right, result);
    }
    return result;
  }
}

// Example Usage
const bst = new BinarySearchTree();
bst.insert(10); // Insert the key 10
bst.insert(5);  // Insert the key 5
bst.insert(15); // Insert the key 15
bst.insert(3);  // Insert the key 3
bst.insert(7);  // Insert the key 7

console.log("Inorder Traversal:", bst.inorderTraversal(bst.root)); // Output: [3, 5, 7, 10, 15]
console.log("Search 7:", bst.search(7) ? "Found" : "Not Found"); // Output: Found
console.log("Search 20:", bst.search(20) ? "Found" : "Not Found"); // Output: Not Found