Lesson 10 / 42
Binary Search Tree
A binary tree where left < node < right, giving ordered O(log n) search.
By Rahul Agarwal · 15 years in web development · Updated 1 Oct 2026
The ordering invariant
For every node, all keys in its left subtree are smaller and all in its right are larger. So searching is like binary search: compare, then go left or right, halving the tree each step — O(h).
Search & insert
Both follow one path from the root; insert drops the new key where the search would have failed.
def search(node, key):
while node and node.val != key:
node = node.left if key < node.val else node.right
return node
def insert(node, key):
if not node: return Node(key)
if key < node.val: node.left = insert(node.left, key)
else: node.right = insert(node.right, key)
return nodeIn-order = sorted
An in-order traversal of a BST yields keys in ascending order. That's a quick way to validate a BST or find the k-th smallest element.
Quick check: Insert 1,2,3,4,5 in order into an empty unbalanced BST. Search cost becomes...
- O(log n)
- O(n)
- O(1)
- O(n log n)
Answer
O(n) — Sorted inserts create a right-leaning chain — effectively a linked list. Balanced trees (AVL, red-black) fix this.