Binary Search Tree

A Binary Search Tree (BST) is a hierarchical data structure where each node has at most two children, with all left descendants less than the current node and all right descendants greater than the current node.

Structure

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

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

Advantages

• Efficient searching (O(log n) on average)
• Maintains sorted order
• Flexible size
• Supports many operations efficiently

Disadvantages

• Can become unbalanced
• No constant-time operations
• More complex than arrays for simple operations
• Not cache-friendly due to non-contiguous memory storage

Common Operations

1. Insert - Add a new value
2. Search - Find a value
3. Delete - Remove a value
4. Traversal - Visit all nodes
   • In-order (Left, Root, Right)
   • Pre-order (Root, Left, Right)
   • Post-order (Left, Right, Root)

Time Complexities

Operation	Average	Worst
Access	O(log n)	O(n)
Search	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)

Implementation Example

Here's a complete implementation of a Binary Search Tree with common operations:

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

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

	// Insert a new value
	insert(value) {
		const newNode = new Node(value);

		if (!this.root) {
			this.root = newNode;
			return this;
		}

		let current = this.root;
		while (true) {
			if (value === current.value) return undefined;
			if (value < current.value) {
				if (!current.left) {
					current.left = newNode;
					return this;
				}
				current = current.left;
			} else {
				if (!current.right) {
					current.right = newNode;
					return this;
				}
				current = current.right;
			}
		}
	}

	// Find a value
	find(value) {
		if (!this.root) return false;

		let current = this.root;
		while (current) {
			if (value === current.value) return true;
			if (value < current.value) {
				current = current.left;
			} else {
				current = current.right;
			}
		}
		return false;
	}

	// In-order traversal
	inOrder() {
		const data = [];

		function traverse(node) {
			if (node.left) traverse(node.left);
			data.push(node.value);
			if (node.right) traverse(node.right);
		}

		if (this.root) traverse(this.root);
		return data;
	}

	// Pre-order traversal
	preOrder() {
		const data = [];

		function traverse(node) {
			data.push(node.value);
			if (node.left) traverse(node.left);
			if (node.right) traverse(node.right);
		}

		if (this.root) traverse(this.root);
		return data;
	}

	// Post-order traversal
	postOrder() {
		const data = [];

		function traverse(node) {
			if (node.left) traverse(node.left);
			if (node.right) traverse(node.right);
			data.push(node.value);
		}

		if (this.root) traverse(this.root);
		return data;
	}
}

Visual Representation

A binary search tree can be visualized as a hierarchical structure:

       8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

Common Use Cases

1. Database Indexing

   • Efficient data retrieval
   • Range queries

2. File Systems

   • Directory structures
   • File organization

3. Applications

   • Expression parsers
   • Priority queues
   • Spell checkers

Practice Problems

To master binary search trees, try solving these common problems:

1. Check if a binary tree is a valid BST
2. Find the kth smallest element
3. Convert sorted array to BST
4. Find lowest common ancestor
5. Balance an unbalanced BST
6. Find closest value in BST

Additional Resources

• Visualgo BST Visualization
• Interactive BST Exercises

Comparison with Other Data Structures

BST vs Array

BST Advantages:

• Better search time (O(log n) vs O(n))
• Dynamic size
• Efficient insertion/deletion

Array Advantages:

• Cache-friendly
• Constant-time access
• Simpler implementation

BST vs Hash Table

BST Advantages:

• Ordered data
• Range queries
• No collision handling needed

Hash Table Advantages:

• O(1) average operations
• Simpler implementation
• Better space efficiency