Binary Search Tree
DSA · Trees
Theory
A binary search tree (BST) is a binary tree where every node's left subtree holds smaller values and its right subtree holds larger values. This ordering lets search, insert and delete follow a single path from the root, taking O(h) time. A balanced BST has height O(log n), but inserting sorted data into a plain BST creates a chain of height n, so operations degrade to O(n). In-order traversal of a BST returns the values in sorted order.
Why we use it
BSTs keep data sorted while supporting fast inserts and searches, plus range queries and min/max.
When to use it
Use BSTs (usually balanced ones, such as TreeMap, red-black trees or B-trees in databases) when you need sorted data with frequent updates.
How it works
- Start at root
- Node is None? Yes: Insert here / not found. No: Compare key with node.
- key == node.key? Yes: Found. No: Go left if smaller, right if larger.
- O(h) per operation, h = height
Syntax
search(n, x):
if n is None or n.val == x: return n
return search(n.left, x) if x < n.val else search(n.right, x)
Search/Insert/Delete: O(h) Balanced h = O(log n)Example
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def insert(root, val):
if root is None:
return Node(val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
def search(root, val):
steps = 0
while root:
steps += 1
if val == root.val:
return True, steps
root = root.left if val < root.val else root.right
return False, steps
def inorder(n):
return inorder(n.left) + [n.val] + inorder(n.right) if n else []
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, v)
print("Sorted:", inorder(root))
print("Search 60:", search(root, 60))
print("Search 65:", search(root, 65))Key points
- Left < node < right
- Operations cost O(height)
- Unbalanced trees degrade to O(n)
- In-order traversal gives sorted output