Mastering Binary Search Trees

Binary Search Trees (BSTs) are fundamental data structures in computer science that provide efficient operations for searching, insertion, and deletion. In this comprehensive guide, we'll explore the inner workings of BSTs and implement them from scratch.

What is a Binary Search Tree?

A Binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

These properties make BSTs particularly useful for search operations, as they allow us to eliminate half of the remaining tree at each step.

Implementing a Binary Search Tree in JavaScript

Let's start by defining the basic structure of our BST:

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // Methods will go here
}
        

Now, let's implement the insertion method:

insert(value) {
  const newNode = new Node(value);
  
  if (this.root === null) {
    this.root = newNode;
    return this;
  }
  
  let current = this.root;
  
  while (true) {
    if (value === current.value) return undefined;
    
    if (value < current.value) {
      if (current.left === null) {
        current.left = newNode;
        return this;
      }
      current = current.left;
    } else {
      if (current.right === null) {
        current.right = newNode;
        return this;
      }
      current = current.right;
    }
  }
}
        

Traversing a Binary Search Tree

There are three main ways to traverse a BST:

1. In-order Traversal

In-order traversal visits the left subtree, then the root, and finally the right subtree. This produces nodes in ascending order for a BST.

inOrder() {
  const result = [];
  
  function traverse(node) {
    if (node.left) traverse(node.left);
    result.push(node.value);
    if (node.right) traverse(node.right);
  }
  
  if (this.root) traverse(this.root);
  return result;
}
        

2. Pre-order Traversal

Pre-order traversal visits the root first, then the left subtree, and finally the right subtree.

preOrder() {
  const result = [];
  
  function traverse(node) {
    result.push(node.value);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  }
  
  if (this.root) traverse(this.root);
  return result;
}
        

3. Post-order Traversal

Post-order traversal visits the left subtree, then the right subtree, and finally the root.

postOrder() {
  const result = [];
  
  function traverse(node) {
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
    result.push(node.value);
  }
  
  if (this.root) traverse(this.root);
  return result;
}
        

Time Complexity Analysis

The time complexity of BST operations depends on the height of the tree:

• Search: O(log n) average case, O(n) worst case
• Insertion: O(log n) average case, O(n) worst case
• Deletion: O(log n) average case, O(n) worst case

The worst case occurs when the tree is skewed (essentially a linked list). To avoid this, balanced BSTs like AVL trees or Red-Black trees are often used in practice.

Practical Applications

Binary Search Trees are used in many applications:

• Implementing associative arrays
• Database indexing
• Priority queues
• Expression evaluation

Conclusion

Binary Search Trees provide an efficient way to store and retrieve data in a sorted manner. By understanding the principles behind BSTs and implementing them correctly, you can significantly improve the performance of your applications.

In our next article, we'll explore balanced BSTs and how they overcome the limitations of standard BSTs.