| name | algo-binary-search-trees |
| description | Implement/debug a binary search tree in Python: insert, search, delete (3 cases), successor/predecessor, inorder/level-order traversal. Use for BST coding, O(log n) vs O(n) degenerate cases, or choosing AVL/Red-Black. |
| tool_type | python |
| primary_tool | Python |
Binary Search Trees (BST)
When to Use
- Implementing a BST from scratch for an interview, assignment, or as a building block for another data structure.
- Explaining or reasoning about BST time complexity (search/insert/delete/traversal) and why sorted input is a worst case.
- Debugging a broken
delete (especially the two-children case) or successor/predecessor logic.
- Deciding whether a plain BST is sufficient or whether you need a self-balancing variant (AVL, Red-Black) for guaranteed O(log n).
- Needing inorder (sorted-order) or level-order (BFS) traversal of a tree of ordered values.
Version Compatibility
Pure Python standard library only — collections.deque, typing. Works on Python ≥3.10 (uses X | None union syntax); for 3.8/3.9 replace with Optional[X].
Prerequisites
- No external packages required.
- Helpful prior concepts:
algo-complexity-analysis (Big-O basics), algo-linear-binary-search (binary search on sorted arrays, for contrast).
- For guaranteed O(log n) instead of amortized/average behavior, see
algo-avl-trees or algo-red-black-trees.
Invariant: for every node, all values in the left subtree < node value < all values in the right subtree (no duplicates stored; duplicates are treated as no-ops on insert).
Complexity
| Operation | Average | Worst (degenerate) |
|---|
| Search / Insert / Delete | O(log n) | O(n) |
| Min / Max | O(log n) | O(n) |
| Successor / Predecessor | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
Worst case occurs on sorted (or reverse-sorted) input, which degenerates the tree into a linked list — use AVL or Red-Black tree to guarantee O(log n).
Goal: a correct, iterative BST supporting search/insert/delete plus ordering queries (min, max, successor, predecessor) and two traversal orders.
Approach: store left/right/parent pointers per node; keep insert/search iterative (O(height) stack-free); implement delete via the classic three-case rule, using _transplant to splice a subtree in place of a node.
from collections import deque
from typing import Any
class Node:
def __init__(self, value: Any) -> None:
self.value = value
self.left = self.right = self.parent = None
class BST:
def __init__(self) -> None:
self.root: Node | None = None
def insert(self, value: Any) -> Node:
"""Insert value, returning the new (or existing, if duplicate) node."""
if not self.root:
self.root = Node(value)
return self.root
node = self.root
while True:
if value < node.value:
if node.left is None:
node.left = Node(value)
node.left.parent = node
return node.left
node = node.left
elif value > node.value:
if node.right is None:
node.right = Node(value)
node.right.parent = node
return node.right
node = node.right
else:
return node
def search(self, value: Any) -> Node | None:
node = self.root
while node:
if value == node.value:
return node
node = node.left if value < node.value else node.right
return None
def find_min(self, node: Node | None = None) -> Node | None:
node = node or self.root
if not node:
return None
while node.left:
node = node.left
return node
def find_max(self, node: Node | None = None) -> Node | None:
node = node or self.root
if not node:
return None
while node.right:
node = node.right
return node
def successor(self, node: Node) -> Node | None:
if node.right:
return self.find_min(node.right)
p = node.parent
while p and node == p.right:
node, p = p, p.parent
return p
def predecessor(self, node: Node) -> Node | None:
if node.left:
return self.find_max(node.left)
p = node.parent
while p and node == p.left:
node, p = p, p.parent
return p
def delete(self, value: Any) -> bool:
"""Delete value if present. Returns True if a node was removed."""
node = self.search(value)
if not node:
return False
self._delete_node(node)
return True
def _delete_node(self, node: Node) -> None:
if node.left and node.right:
succ = self.find_min(node.right)
node.value = succ.value
self._delete_node(succ)
else:
child = node.left or node.right
self._transplant(node, child)
def _transplant(self, u: Node, v: Node | None) -> None:
"""Replace subtree rooted at u with subtree rooted at v."""
if not u.parent:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
if v:
v.parent = u.parent
def inorder(self) -> list[Any]:
"""Return values in sorted order."""
result: list[Any] = []
def _rec(n):
if n:
_rec(n.left)
result.append(n.value)
_rec(n.right)
_rec(self.root)
return result
def level_order(self) -> list[Any]:
"""Return values in BFS (level-by-level) order."""
if not self.root:
return []
result, q = [], deque([self.root])
while q:
n = q.popleft()
result.append(n.value)
if n.left:
q.append(n.left)
if n.right:
q.append(n.right)
return result
def __contains__(self, value: Any) -> bool:
return self.search(value) is not None
def demo() -> None:
"""Self-check: build a tree, verify invariants hold after insert/delete."""
bst = BST()
for v in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(v)
assert bst.inorder() == [20, 30, 40, 50, 60, 70, 80]
assert 40 in bst and 999 not in bst
n40 = bst.search(40)
assert bst.successor(n40).value == 50
assert bst.predecessor(n40).value == 30
assert bst.delete(30) is True
assert 30 not in bst
assert bst.inorder() == [20, 40, 50, 60, 70, 80]
assert bst.delete(999) is False
print("All BST checks passed.")
if __name__ == "__main__":
demo()
Delete: Three Cases
| Node type | Action |
|---|
| Leaf | Remove directly (transplant with None) |
| One child | Replace node with that child |
| Two children | Copy inorder successor's value into the node, then delete the successor (which has at most one child) |
Pitfalls
- Sorted input degenerates to O(n): inserting
[1,2,3,4,5] creates a linked list; use a self-balancing tree (AVL, Red-Black) for production use where input order isn't controlled.
- Inorder successor during deletion: after copying the successor's value to the deleted node, you must delete the successor node — not the original node again (recursing on
succ, not node, avoids this).
- Parent pointer consistency: when implementing with parent pointers, only set
v.parent in _transplant if v is not None, or you'll crash on leaf deletion.
- Recursive height/traversal on deep trees: Python's default recursion limit (~1000) is hit on degenerate (near-linear) trees; use iterative traversal (e.g. an explicit stack, like
level_order's BFS) for untrusted input sizes.
- Duplicates: this implementation silently ignores inserting a value already present; decide explicitly whether your use case needs a count/multiset instead.
See Also
algo-avl-trees — self-balancing BST guaranteeing O(log n) via rotations.algo-red-black-trees — another self-balancing BST, used by many standard library map/set implementations.algo-linear-binary-search — binary search over a sorted array (no explicit tree structure).algo-complexity-analysis — Big-O fundamentals referenced throughout this skill.
