A
AiTechWorlds
AiTechWorlds
Before smartphones, everyone had a phone book — a thick directory of names and numbers sorted alphabetically. To find "Smith, John," you would not start at page one and flip through every name. You would open to the middle. If the middle page showed names starting with "M," you knew Smith was in the right half. You opened to the middle of the right half. Maybe that showed "R" names — so Smith is in the right half again. Three or four splits and you were there.
You just performed binary search. A Binary Search Tree (BST) bakes this same logic into the structure of the tree itself. Every node encodes a decision: go left if smaller, go right if larger. Every step cuts the remaining possibilities in half.
BST Property: For every node N in the tree:
- All values in N's left subtree are less than N's value.
- All values in N's right subtree are greater than N's value.
- Both subtrees are also valid BSTs (the property applies recursively).
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Check node 3: everything to its left (just 1) is less than 3. Everything to its right (6, 4, 7) is greater than 3. The property holds at every node.
This ordering property means search is always directed — you never need to look at both subtrees simultaneously.
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
# --- Insert: place a new value in the correct position ---
def insert(self, val):
if self.root is None:
self.root = TreeNode(val) # Empty tree — new node becomes root
else:
self._insert(self.root, val)
def _insert(self, node, val):
if val < node.val: # Value belongs in the LEFT subtree
if node.left is None:
node.left = TreeNode(val) # Empty slot found — insert here
else:
self._insert(node.left, val) # Keep going left
elif val > node.val: # Value belongs in the RIGHT subtree
if node.right is None:
node.right = TreeNode(val)
else:
self._insert(node.right, val)
# If val == node.val, we ignore duplicates (standard BST behavior)
# --- Search: find whether a value exists ---
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if node is None:
return False # Fell off the tree — not found
if val == node.val:
return True # Found it!
elif val < node.val:
return self._search(node.left, val) # Must be in left subtree
else:
return self._search(node.right, val)# Must be in right subtree
# --- In-order traversal: visits nodes in SORTED order ---
def inorder(self, node=None, first_call=True):
if first_call:
node = self.root
if node:
self.inorder(node.left, first_call=False) # Left subtree first
print(node.val, end=" ") # Then current node
self.inorder(node.right, first_call=False) # Then right subtree
# --- Delete: remove a node while maintaining BST property ---
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if node is None:
return None # Value not found — nothing to delete
if val < node.val: # Target is in left subtree
node.left = self._delete(node.left, val)
elif val > node.val: # Target is in right subtree
node.right = self._delete(node.right, val)
else:
# CASE 1: Node has no children (it is a leaf)
if node.left is None and node.right is None:
return None # Simply remove it
# CASE 2: Node has one child
elif node.left is None:
return node.right # Replace node with its right child
elif node.right is None:
return node.left # Replace node with its left child
# CASE 3: Node has two children
# Find the in-order successor (smallest value in the right subtree)
successor = self._find_min(node.right)
node.val = successor.val # Copy successor's value here
node.right = self._delete(node.right, successor.val) # Remove successor
return node
def _find_min(self, node):
while node.left: # Keep going left to find the minimum
node = node.left
return node
Deleting from a BST is the trickiest operation because you must maintain the BST property after removal.
| Case | Situation | Solution |
|---|---|---|
| Case 1 | Node has no children (leaf) | Simply remove the node |
| Case 2 | Node has one child | Replace node with its only child |
| Case 3 | Node has two children | Replace with in-order successor (smallest in right subtree), then delete the successor |
Case 3 in detail: If you delete node 3 from the tree above, you find its in-order successor (4 — the smallest value larger than 3). You copy 4 into node 3's position, then delete the original node 4 from the right subtree.
bst = BST()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(val)
print("In-order traversal (sorted):")
bst.inorder()
print()
print("Search 6:", bst.search(6)) # True
print("Search 5:", bst.search(5)) # False
bst.delete(3)
print("After deleting 3:")
bst.inorder()
print()
Output:
In-order traversal (sorted):
1 3 4 6 7 8 10 13 14
Search 6: True
Search 5: False
After deleting 3:
1 4 6 7 8 10 13 14
The in-order traversal of a BST always produces a sorted sequence. This is one of the most elegant properties in the data structure.
| Operation | Balanced BST | Unbalanced (Degenerate) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min/Max | O(log n) | O(n) |
| In-order | O(n) | O(n) |
| Feature | BST | Sorted Array |
|---|---|---|
| Search | O(log n) | O(log n) binary search |
| Insert | O(log n) | O(n) — must shift elements |
| Delete | O(log n) | O(n) — must shift elements |
| Memory | Extra pointers | Compact |
| In-order traversal | O(n) | O(n) |
| Best for | Frequent inserts/deletes | Mostly static data |
Use a BST when your data changes frequently. Use a sorted array when you build it once and only read.
Here is the danger with BSTs: the order of insertion determines the shape of the tree.
# Inserting sorted data creates a degenerate tree — basically a linked list
bst2 = BST()
for val in [1, 2, 3, 4, 5]:
bst2.insert(val)
# Tree looks like:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
This tree has height 4 instead of the ideal 2. Every operation is now O(n) instead of O(log n). This is the degenerate case — the BST has become a linked list.
To prevent degeneration, self-balancing BSTs automatically restructure themselves on every insert and delete to maintain a balanced height.
AVL Trees — After every insertion or deletion, the tree checks the height difference between left and right subtrees at every node. If the difference exceeds 1, it performs a rotation to rebalance. Strict balance: always O(log n).
Red-Black Trees — Each node is colored red or black. Color rules guarantee the tree never gets more than twice as tall as it needs to be. Slightly less strict than AVL, but faster to insert and delete. Python's sorted containers library and Java's TreeMap use Red-Black trees.
You do not need to implement these yourself — understanding the concept is what matters. The key insight: a balanced BST has O(log n) for all core operations, always.
A Binary Search Tree stores ordered data in a structure where every search decision — left or right — cuts the remaining work in half. This gives O(log n) performance for search, insert, and delete on a balanced tree. The in-order traversal always produces a sorted sequence, which is both beautiful and useful. The main risk is degeneration on sorted input — self-balancing variants like AVL and Red-Black trees exist precisely to prevent this.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises