Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Binary search trees: preserve order through every branch

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary search tree stores a key at each node, with smaller keys in its left subtree and larger keys in its right subtree under a chosen duplicate policy. Search follows one branch per level and costs O(h) for tree height h. A balanced tree has h = O(log n); ordinary insertion without rebalancing can create a chain with h = O(n). The invariant applies to whole subtrees, not just immediate children. A duplicate key must either replace an associated value, increment a count, or be rejected; leaving that behavior implicit breaks search and traversal assumptions.

Operational case

A parts catalog inserts keys 52, 47, 61, and 58. Searching for 58 visits 52, then 61, then 58. Its in-order traversal is 47, 52, 58, 61, confirming the chosen ordering on this fixture. If future uploads arrive in ascending order, a plain tree degenerates and no longer provides logarithmic lookup. A production catalog might prefer a balanced tree or database index; the simple code exposes the ordering rule without pretending it maintains balance.

Working Python program

python
class PartNode:
    def __init__(self, part_code):
        self.part_code = part_code
        self.left = None
        self.right = None

root = PartNode(52)
for part_code in (47, 61, 58):
    current = root
    while True:
        side = "left" if part_code < current.part_code else "right"
        child = getattr(current, side)
        if child is None:
            setattr(current, side, PartNode(part_code))
            break
        current = child
current = root
visited = []
while current is not None:
    visited.append(current.part_code)
    current = current.left if 58 < current.part_code else current.right if 58 > current.part_code else None
    if visited[-1] == 58:
        break
print(visited)

Output

Output
[52, 61, 58]

Time, space, and tradeoff

Insertion and lookup each cost O(h) time and O(1) extra space in this iterative example. The structure stores O(n) nodes and references. The code assumes unique keys; a production insertion method should explicitly reject or replace duplicates and test the path where a key equals an existing node. Deletion needs extra cases for zero, one, or two children and must reconnect subtrees without violating their global bounds. To guarantee logarithmic height, use a balancing scheme rather than hoping insertion order stays favorable.

Common Mistakes

  • Do not claim an unbalanced search tree always has O(log n) lookup.
  • Do not check only immediate children when validating order.
  • Do not let duplicate keys take an undocumented branch.

Connected lessons

Binary-tree traversals: four orders without recursion adds a related operation contract.

Splay Trees: Access Rotations and Join Invariants extends this operation comparison.

data structures
trees-and-heaps
Storage details