Binary search trees
Binary Search Trees: definitions, properties, operations (search/insert/delete), traversal, complexity, and Python programs that build, query, and modify BSTs.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Binary Search Trees (BSTs) are used whenever you need to store items with keys and support fast search, insert and delete, such as in symbol tables, in-memory indices of databases, and language runtimes. They also give the conceptual foundation for balanced trees (like AVL, Red–Black) and ordered data structures (sets, maps) used in compilers, operating systems and backend services.
Key ideas
- Node: A record that holds a key (a comparable value) and optionally satellite data, and references to its left and right child.
- Key: A value drawn from a totally ordered domain (e.g., integers, strings with lexicographic order) used to compare nodes.
- Root: The unique topmost node of a tree.
- Child and parent: If node u is directly under node v, u is a child of v and v is the parent of u.
- Leaf: A node with no children.
- Subtree: A node together with all its descendants.
- Path: A sequence of nodes connected by parent–child links.
- Depth of a node: The number of edges on the path from the root to that node (root has depth 0).
- Height of a tree: The number of edges on the longest root-to-leaf path. By convention here, an empty tree has height −1; a single-node tree has height 0.
- Binary Search Tree (BST): A binary tree in which every node x satisfies the BST property: all keys in x’s left subtree are strictly less than key(x), and all keys in x’s right subtree are strictly greater than key(x). Duplicates are handled by a convention (e.g., either disallow, or keep duplicates consistently on one fixed side). Assumption: the key type has a total order and the comparison is transitive, antisymmetric, and total.
- The BST property (formal statement): For every node x, and for every node y in the left subtree of x, key(y) < key(x); for every node z in the right subtree of x, key(x) < key(z). This is an invariant preserved by correct search, insertion, and deletion. If duplicates are permitted by policy on a fixed side, modify the inequalities accordingly (e.g., left subtree keys ≤ key(x) and right subtree keys > key(x), or left subtree keys < key(x) and right subtree keys ≥ key(x)); state your choice explicitly.
- Inorder traversal: A traversal that visits the left subtree, then the node, then the right subtree.
- Theorem (Inorder traversal yields sorted order in a BST): For a BST containing keys from a totally ordered set and with the BST property holding at every node, an inorder traversal visits the keys in strictly increasing order. If duplicates are allowed by convention, inorder yields a non-decreasing sequence (equal keys appear consecutively).
- Proof (by structural induction):
- Base: An empty tree yields an empty sequence, which is sorted.
- Induction step: Assume the theorem holds for BSTs with fewer than n nodes. Consider a BST T with root r, left subtree L, right subtree R. By the BST property, all keys in L are < key(r) < all keys in R. By the induction hypothesis, inorder(L) is sorted and inorder(R) is sorted. Concatenating inorder(L), key(r), inorder(R) preserves sorted order because every element of inorder(L) < key(r) < every element of inorder(R). Hence inorder(T) is sorted.
- Proof (by structural induction):
- Search in a BST: Compare the target key k with the current node’s key. If k equals it, success. If k is less, go to the left child; if greater, go to the right child. Stop when found or when reaching a null child (not found). Time complexity is proportional to the length of the root-to-node path traversed.
- Insert in a BST: Follow the search path for key k. When you would descend to a null child, create a new node there with key k (respect the duplicate policy: disallow or place on a fixed side consistently). This preserves the BST property because all nodes left of the insertion point are still < k and all to the right are > k.
- Delete in a BST: To delete a node with key k, first find it. Three exhaustive cases:
- Node has no children (leaf): remove it by making its parent’s pointer null.
- Node has exactly one child: replace the node by its child (link the parent to that child).
- Node has two children: replace the node’s key (and satellite data) with its inorder successor’s key (the minimum in the node’s right subtree) or inorder predecessor’s key (the maximum in the left subtree), and then delete that successor/predecessor node, which will fall into case 1 or 2. This preserves the BST property because the successor is the smallest key greater than the node’s key.
- Successor of a node x in a BST: The smallest key strictly greater than key(x). If x has a right subtree, it is the minimum in that right subtree; otherwise, go up via parents until you move up from a left child; that parent is the successor.
- Predecessor of a node x: The largest key strictly smaller than key(x). If x has a left subtree, it is the maximum in that left subtree; otherwise, go up via parents until you move up from a right child; that parent is the predecessor.
- Height-driven cost: Let h be height(T). Any root-to-leaf path length is at most h, so search/insert/delete take O(h) time. Worst case h = n − 1 for a chain (skewed tree), giving O(n). Best/typical for well-balanced trees, h ≈ ⌊log₂ n⌋, giving O(log n). For random insert orders without rebalancing, the expected height is O(log n), though with a larger constant factor than strictly balanced trees.
- Space: A BST with n nodes uses O(n) space; typical linked-node implementations use two references per node (left and right), or three if a parent pointer is stored, plus key and data. Recursive traversals/operations use O(h) auxiliary stack space.
- Diagram to draw (exam): Draw a root node as a circle labeled with its key. Draw a left child subtree with all keys less than the root on the left side and a right child subtree with all keys greater than the root on the right side. For deletion case 3, draw a node with two children; show its right subtree; mark its inorder successor as the leftmost node of the right subtree; draw an arrow copying the successor’s key into the deleted node; then delete the successor node (it has no left child; if it has a right child, link it to its parent).
Derivations commonly asked
- Derivation of O(h) complexity: Each comparison at a node determines a unique next node (left or right). The algorithm descends one level per comparison, so at most one comparison per level; the number of levels visited is at most h + 1 nodes, so time ∈ Θ(h + 1) = Θ(h).
- Correctness of delete (two-child case): The inorder successor s is greater than all keys in the left subtree (by transitivity and BST property) and is the minimum of the right subtree, so no key in the right subtree is less than s. Replacing the node’s key by s preserves the property locally; deleting s from the right subtree preserves the property inductively.
Formulas
Programming syntax and facts to remember (no SI units):
class Node: __init__(self, key, left=None, right=None)— Node structure with a key and two child references.if k < node.key: node = node.left elif k > node.key: node = node.right else: found— One BST search step using total order comparisons.insert: Follow search path until a None pointer; attach new Node there; duplicates either disallowed or consistently placed (state your policy).delete (0/1 child): Replace node by its single child or None.delete (2 children):succ = min(node.right);node.key = succ.key; deletesuccfrom right subtree.min(node): Go left untilnode.left is None.max(node): Go right untilnode.right is None.successor(node): Ifnode.right, returnmin(node.right); else move up via parents until you traverse a left edge; that parent is the successor.inorder(node): Recurse left, visit node, recurse right → sorted output for BST.height(T): Number of edges on the longest root-to-leaf path; for empty tree, height = −1; for single node, height = 0.- Time complexities:
search = insert = delete = O(h); worst-caseO(n); balanced heighth ≈ ⌊log₂ n⌋.
Worked examples
Example 1 — Build a BST, print inorder, height, and search result Python program:
# Build a BST from input, print inorder traversal, height, and search result
import sys
sys.setrecursionlimit(10000)
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
# if equal, ignore duplicate (policy: disallow duplicates)
return root
def inorder(root, out):
if root is None:
return
inorder(root.left, out)
out.append(str(root.key))
inorder(root.right, out)
def height(root):
if root is None:
return -1 # empty tree
return 1 + max(height(root.left), height(root.right))
def search(root, key):
cur = root
while cur is not None:
if key < cur.key:
cur = cur.left
elif key > cur.key:
cur = cur.right
else:
return True
return False
# Input format:
# n\n
# n space-separated integers\n
# q (key to search)\n
n = int(sys.stdin.readline().strip())
vals = list(map(int, sys.stdin.readline().strip().split()))
q = int(sys.stdin.readline().strip())
root = None
for v in vals[:n]:
root = insert(root, v)
io = []
inorder(root, io)
print("Inorder:", " ".join(io))
print("Height:", height(root))
print(f"Search {q}:", "Found" if search(root, q) else "Not found")
Sample input:
7
50 30 70 20 40 60 80
60
Exact output:
Inorder: 20 30 40 50 60 70 80
Height: 2
Search 60: Found
Example 2 — Delete a key from a BST and print inorder traversal Python program:
# Build a BST, delete a key (handles 0, 1, or 2 children), then print inorder
import sys
sys.setrecursionlimit(10000)
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def find_min(node):
cur = node
while cur.left is not None:
cur = cur.left
return cur
def delete(root, key):
if root is None:
return None
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
# Found node to delete
if root.left is None and root.right is None:
return None
elif root.left is None:
return root.right
elif root.right is None:
return root.left
else:
succ = find_min(root.right)
root.key = succ.key
root.right = delete(root.right, succ.key)
return root
def inorder(root, out):
if root is None:
return
inorder(root.left, out)
out.append(str(root.key))
inorder(root.right, out)
# Input format:
# n\n
# n space-separated integers\n
# d (key to delete)\n
n = int(sys.stdin.readline().strip())
vals = list(map(int, sys.stdin.readline().strip().split()))
d = int(sys.stdin.readline().strip())
root = None
for v in vals[:n]:
root = insert(root, v)
root = delete(root, d)
io = []
inorder(root, io)
print("Inorder after delete:", " ".join(io))
Sample input:
7
50 30 70 20 40 60 80
30
Exact output:
Inorder after delete: 20 40 50 60 70 80
Example 3 — Find the k-th smallest key in a BST Python program:
# Build a BST and print the k-th smallest element (1-indexed); report invalid k
import sys
sys.setrecursionlimit(10000)
class Node:
__slots__ = ("key", "left", "right")
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def kth_smallest(root, k):
# Iterative inorder to avoid deep recursion output management
stack = []
cur = root
count = 0
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
count += 1
if count == k:
return cur.key
cur = cur.right
return None
# Input format:
# n\n
# n space-separated integers\n
# k\n
n = int(sys.stdin.readline().strip())
vals = list(map(int, sys.stdin.readline().strip().split()))
k = int(sys.stdin.readline().strip())
root = None
for v in vals[:n]:
root = insert(root, v)
ans = kth_smallest(root, k)
if ans is None:
print("Invalid k")
else:
print(ans)
Sample input:
7
50 30 70 20 40 60 80
4
Exact output:
50
Common mistakes
- Mixing up height definitions (nodes vs edges). Always define your convention; here: edges, empty tree = −1.
- In deletion with two children, copying the successor’s key but forgetting to delete the successor node from the right subtree.
- Returning the inorder successor incorrectly (e.g., right child directly, instead of the minimum in the right subtree).
- Writing inorder traversal that prints in sorted order for any binary tree (this is only true for BSTs).
- Assuming O(log n) always, ignoring the worst case O(n) when the tree is skewed (e.g., inserting sorted keys into an empty BST).
- Not handling None checks in recursive functions, leading to runtime errors.
- In code, allowing duplicates inconsistently (sometimes left, sometimes right), which can break search correctness.
For your exam
- Short notes: Prove that inorder traversal of a BST gives sorted order (use induction), explain delete cases with a neat diagram, explain time complexities in terms of height h and relate h to n in best/worst cases.
- Derivations/Proofs: Correctness of deletion (especially two-children case), complexity Θ(h) from path length argument.
- Programs: Implement search/insert/delete; produce inorder traversal of a given insertion sequence; compute height; find k-th smallest. Include clear input format, correct handling of duplicates, and exact output formatting.
- Diagrams: Draw small BSTs that illustrate balanced vs skewed trees; show paths taken by search; show the inorder successor/predecessor locations.
- What full marks answers include: clear definition of terms, stated assumptions, stepwise algorithms, correct case analysis for deletion, complexity with justification, clean diagrams with labels (left/right, successor/predecessor), and correct, well-formatted code/output where asked.
Quick check
- State the BST property formally.
- What is the height (edges) of an empty tree and of a single-node tree under the convention used in these notes?
- In the delete operation, how do you find the inorder successor of a node with two children?
Answers: 1) For every node x, all keys in the left subtree are < key(x) and all in the right subtree are > key(x); 2) Empty = −1, single-node = 0; 3) If the node has a right subtree, the successor is the minimum key in that right subtree (leftmost node of the right subtree).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?