Introduction to Binary Search Tree
A Binary Search Tree (BST) is a binary tree with a special ordering property that makes searching efficient:
How a BST Works
A Binary Search Tree (BST) is a specialized version of a Binary Tree designed for rapid searching, inserting, and deleting. It strictly follows a specific ordering property:
- The Left Rule: Everything in the left subtree of a node must have a value less than the parent node.
- The Right Rule: Everything in the right subtree of a node must have a value greater than the parent node.
- No Duplicates: Standard BSTs typically do not allow duplicate values.
Because of this built-in sorting logic, you can easily navigate the tree by asking “Is the value I’m looking for smaller or larger than my current position?”
Real-Life Examples
- Finding a Word in a Dictionary: You don’t read a dictionary page by page. You open it to the middle. If your word comes earlier in the alphabet, you ignore the entire right half of the book and split the left half. You repeat this until you find the word.
- The “Guess My Number” Game: If someone says “Guess a number between 1 and 100,” you start at 50. If they say “Higher,” you instantly eliminate 1 through 50 and guess 75. A BST automates this exact elimination process.
Technical & Software Applications
- Database Indexing: When you query a massive database (like finding a specific user ID among millions), the database uses tree structures (often B-Trees, a more complex cousin of the BST) to find the record in milliseconds without scanning every row.
- Auto-Complete and Spell Checkers: Applications use specialized search trees to quickly predict the word you are typing or verify if a word exists in the dictionary.
- 3D Rendering: Graphics engines use search trees to quickly determine which objects in a 3D environment are closest to the camera and need to be drawn first.
Time and Space Complexity
- Time Complexity (Average): $O(\log n)$ for searching, inserting, and deleting. With every step down the tree, you eliminate half of the remaining possibilities.
- Time Complexity (Worst Case): O(n). If you insert already-sorted data (like 1, 2, 3, 4, 5) into a basic BST, it just forms a straight line (a skewed tree), completely losing its efficiency and degrading into a standard Linked List.
- Space Complexity: O(n) because memory scales linearly with the number of nodes.
Visual Example
Valid BST: Invalid BST:
50 50
/ \ / \
30 70 30 70
/ \ / \ / \ / \
20 40 60 80 20 65 60 80
↑
(65 > 50, should be in right)Why Use BST?
Advantages:
- Efficient searching: O(log n) average case
- Maintains sorted order (inorder traversal gives sorted sequence)
- Dynamic size (can grow/shrink)
- Efficient insertion and deletion
Use Cases:
- Dictionary implementations
- Database indexing
- Priority queues
- Auto-complete features
- File system organization
Properties and Characteristics
1. BST Node Structure
Code Example :
JavaPythonCC++
class BSTNode {
int data;
BSTNode left;
BSTNode right;
// Constructor
public BSTNode(int value) {
this.data = value;
this.left = null;
this.right = null;
}
}
class BSTNode:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
#include <stdio.h>
#include <stdlib.h>
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
// Constructor equivalent
struct BSTNode* createNode(int value) {
struct BSTNode* newNode = (struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
#include <iostream>
using namespace std;
class BSTNode {
public:
int data;
BSTNode* left;
BSTNode* right;
// Constructor
BSTNode(int value) {
this->data = value;
this->left = NULL;
this->right = NULL;
}
};
2. Key Properties
Code Example :
JavaPythonCC++
class BSTProperties {
// Property 1: Inorder traversal gives sorted sequence
static void demonstrateInorderProperty() {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(40);
bst.insert(60);
bst.insert(80);
System.out.println("Inorder traversal (sorted):");
bst.inorder(bst.root); // Output: 20 30 40 50 60 70 80
}
// Property 2: For every node, left subtree < node < right subtree
static boolean verifyBSTProperty(BSTNode root, Integer min, Integer max) {
// Base case: empty tree is BST
if (root == null)
return true;
// Check current node's value
if ((min != null && root.data = max))
return false;
// Recursively check left and right subtrees
return verifyBSTProperty(root.left, min, root.data) &&
verifyBSTProperty(root.right, root.data, max);
}
// Property 3: Minimum is leftmost, Maximum is rightmost
static int findMin(BSTNode root) {
if (root == null)
throw new IllegalStateException("Empty tree");
while (root.left != null)
root = root.left;
return root.data;
}
static int findMax(BSTNode root) {
if (root == null)
throw new IllegalStateException("Empty tree");
while (root.right != null)
root = root.right;
return root.data;
}
}
class BSTProperties:
# Property 1: Inorder traversal gives sorted sequence
@staticmethod
def demonstrateInorderProperty():
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(70)
bst.insert(20)
bst.insert(40)
bst.insert(60)
bst.insert(80)
print("Inorder traversal (sorted):")
bst.inorder(bst.root) # Output: 20 30 40 50 60 70 80
# Property 2: For every node, left subtree < node < right subtree
@staticmethod
def verifyBSTProperty(root, min_val, max_val):
if root is None:
return True
if (min_val is not None and root.data = max_val):
return False
return BSTProperties.verifyBSTProperty(root.left, min_val, root.data) and \
BSTProperties.verifyBSTProperty(root.right, root.data, max_val)
# Property 3: Minimum is leftmost, Maximum is rightmost
@staticmethod
def findMin(root):
if root is None:
raise Exception("Empty tree")
while root.left is not None:
root = root.left
return root.data
@staticmethod
def findMax(root):
if root is None:
raise Exception("Empty tree")
while root.right is not None:
root = root.right
return root.data
#include <stdio.h>
#include <stdlib.h>
struct BSTNode {
int data;
struct BSTNode* left;
struct BSTNode* right;
};
// Property 2: Verify BST property
int verifyBSTProperty(struct BSTNode* root, int min, int max) {
if (root == NULL)
return 1;
if (root->data data >= max)
return 0;
return verifyBSTProperty(root->left, min, root->data) &&
verifyBSTProperty(root->right, root->data, max);
}
// Property 3: Find minimum
int findMin(struct BSTNode* root) {
if (root == NULL) {
printf("Empty tree\n");
exit(1);
}
while (root->left != NULL)
root = root->left;
return root->data;
}
// Property 3: Find maximum
int findMax(struct BSTNode* root) {
if (root == NULL) {
printf("Empty tree\n");
exit(1);
}
while (root->right != NULL)
root = root->right;
return root->data;
}
#include <iostream>
#include <climits>
using namespace std;
class BSTProperties {
public:
// Property 2: Verify BST property
static bool verifyBSTProperty(BSTNode* root, int min, int max) {
if (root == NULL)
return true;
if (root->data data >= max)
return false;
return verifyBSTProperty(root->left, min, root->data) &&
verifyBSTProperty(root->right, root->data, max);
}
// Property 3: Minimum is leftmost
static int findMin(BSTNode* root) {
if (root == NULL)
throw runtime_error("Empty tree");
while (root->left != NULL)
root = root->left;
return root->data;
}
// Property 3: Maximum is rightmost
static int findMax(BSTNode* root) {
if (root == NULL)
throw runtime_error("Empty tree");
while (root->right != NULL)
root = root->right;
return root->data;
}
};
Basic Operations
Complete BST Implementation
Code Example :
JavaPythonCC++
import java.util.*;
// Node of BST
class BSTNode {
int data;
BSTNode left, right;
BSTNode(int value) {
data = value;
left = right = null;
}
}
class BinarySearchTree {
BSTNode root;
// ===== INSERT =====
// Insert a value into BST
BSTNode insert(BSTNode node, int key) {
// If position found, create node
if (node == null)
return new BSTNode(key);
// Go left or right
if (key < node.data)
node.left = insert(node.left, key);
else if (key > node.data)
node.right = insert(node.right, key);
return node;
}
void insert(int key) {
root = insert(root, key);
}
// ===== SEARCH =====
boolean search(BSTNode node, int key) {
if (node == null)
return false;
if (node.data == key)
return true;
if (key < node.data)
return search(node.left, key);
else
return search(node.right, key);
}
// ===== FIND MIN (used in deletion) =====
int findMin(BSTNode node) {
while (node.left != null)
node = node.left;
return node.data;
}
// ===== DELETE =====
BSTNode delete(BSTNode node, int key) {
if (node == null)
return null;
if (key < node.data)
node.left = delete(node.left, key);
else if (key > node.data)
node.right = delete(node.right, key);
else {
// Case 1: no child
if (node.left == null && node.right == null)
return null;
// Case 2: one child
if (node.left == null)
return node.right;
if (node.right == null)
return node.left;
// Case 3: two children
node.data = findMin(node.right);
node.right = delete(node.right, node.data);
}
return node;
}
// ===== INORDER (sorted output) =====
void inorder(BSTNode node) {
if (node == null)
return;
inorder(node.left);
System.out.print(node.data + " ");
inorder(node.right);
}
// ===== LEVEL ORDER (BFS) =====
void levelOrder() {
if (root == null)
return;
Queue<BSTNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
BSTNode temp = q.poll();
System.out.print(temp.data + " ");
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
}
}
from collections import deque
# Node of BST
class BSTNode:
def __init__(self, value):
self.data = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
# ===== INSERT =====
def insert(self, node, key):
if node is None:
return BSTNode(key)
if key < node.data:
node.left = self.insert(node.left, key)
elif key > node.data:
node.right = self.insert(node.right, key)
return node
# ===== SEARCH =====
def search(self, node, key):
if node is None:
return False
if node.data == key:
return True
if key < node.data:
return self.search(node.left, key)
else:
return self.search(node.right, key)
# ===== FIND MIN =====
def findMin(self, node):
while node.left:
node = node.left
return node.data
# ===== DELETE =====
def delete(self, node, key):
if node is None:
return None
if key < node.data:
node.left = self.delete(node.left, key)
elif key > node.data:
node.right = self.delete(node.right, key)
else:
if node.left is None:
return node.right
if node.right is None:
return node.left
node.data = self.findMin(node.right)
node.right = self.delete(node.right, node.data)
return node
# ===== INORDER =====
def inorder(self, node):
if node is None:
return
self.inorder(node.left)
print(node.data, end=" ")
self.inorder(node.right)
# ===== LEVEL ORDER =====
def levelOrder(self):
if self.root is None:
return
q = deque([self.root])
while q:
temp = q.popleft()
print(temp.data, end=" ")
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// Create new node
struct Node* createNode(int value) {
struct Node* n = malloc(sizeof(struct Node));
n->data = value;
n->left = NULL;
n->right = NULL;
return n;
}
// Insert into BST
struct Node* insert(struct Node* root, int key) {
if (root == NULL)
return createNode(key);
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
return root;
}
// Inorder traversal
void inorder(struct Node* root) {
if (root == NULL)
return;
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
#include <iostream>
#include <queue>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = right = NULL;
}
};
class BinarySearchTree {
public:
Node* root;
BinarySearchTree() {
root = NULL;
}
// INSERT
Node* insert(Node* node, int key) {
if (node == NULL)
return new Node(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
return node;
}
// INORDER
void inorder(Node* node) {
if (node == NULL)
return;
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
// LEVEL ORDER
void levelOrder() {
if (root == NULL)
return;
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
cout << temp->data << " ";
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
}
};