Python Tutorial
Binary Search Trees (BST)
An ordered binary tree that keeps values sorted, enabling O(log n) search, insert, and delete when balanced.
The BST Property
A binary search tree enforces one rule at every node: all values in the left subtree are smaller, all values in the right subtree are larger. This ordering lets you discard half the remaining tree at each step, just like binary search on a sorted array.
Insertion
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(root, value):
if root is None:
return Node(value)
if value < root.value:
root.left = insert(root.left, value)
elif value > root.value:
root.right = insert(root.right, value)
return root # duplicates ignored
root = None
for v in [50, 30, 70, 20, 40, 60, 80]:
root = insert(root, v)Search
def search(root, value):
if root is None or root.value == value:
return root
if value < root.value:
return search(root.left, value)
return search(root.right, value)
print(search(root, 60) is not None) # True
print(search(root, 45) is not None) # FalseEach comparison halves the search space, so a balanced BST searches in O(log n).
In-Order Traversal Gives Sorted Order
def inorder(root, out):
if root:
inorder(root.left, out)
out.append(root.value)
inorder(root.right, out)
return out
print(inorder(root, [])) # [20, 30, 40, 50, 60, 70, 80]Deletion: Three Cases
Removing a node must preserve the BST property. Its in-order successor (smallest value in the right subtree) replaces a node with two children.
def min_node(node):
while node.left:
node = node.left
return node
def delete(root, value):
if root is None:
return None
if value < root.value:
root.left = delete(root.left, value)
elif value > root.value:
root.right = delete(root.right, value)
else:
if root.left is None: # 0 or 1 child
return root.right
if root.right is None:
return root.left
succ = min_node(root.right) # 2 children
root.value = succ.value
root.right = delete(root.right, succ.value)
return root
root = delete(root, 30)The Balance Problem
Inserting sorted data (1, 2, 3, 4, …) turns a BST into a straight line — height n, so operations degrade to O(n). Self-balancing variants fix this by restructuring after each change.
| Operation | Balanced | Degenerate (sorted input) |
|---|---|---|
| Search / Insert / Delete | O(log n) | O(n) |
A plain BST guarantees ordering, not balance. For worst-case O(log n), use a self-balancing tree (AVL, Red-Black) — covered next.
Best Practices
- Use a BST when you need sorted order plus fast search/insert/delete.
- Shuffle or balance input to avoid degenerate chains.
- In Python,
sortedcontainers.SortedListgives BST-like performance without hand-coding one. - Remember the in-order = sorted property for range queries and k-th smallest.
Try It Yourself
Exercise 1: Insert 8, 3, 10, 1, 6 into a BST. What is the root's left child?
Show solution
3 — values smaller than the root (8) go left; 3 is the first such value and becomes the left child.
Exercise 2: What happens to a BST's performance if you insert already-sorted data?
Show solution
It degenerates into a linked list (height n), so operations become O(n). Use a self-balancing tree (AVL) to prevent this.
📘 Real-World Deep Dive
Knowing <strong>DSA Bst (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Bst that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
class BST:
def __init__(self, val=None):
self.val = val
self.left = self.right = None
def insert(self, x):
if self.val is None:
self.val = x; return
cur = self
while True:
if x < cur.val:
if cur.left is None: cur.left = BST(x); return
cur = cur.left
else:
if cur.right is None: cur.right = BST(x); return
cur = cur.right
b = BST()
for v in [7,3,9,1,5,8,10]:
b.insert(v)
# (depth.manual print to keep example small)
print("root:", b.val, "left child:", b.left.val, "right child:", b.right.val)Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Bst as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.