Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 8

Binary search trees and traversals

Use subtree ordering rather than local guesses, and express search cost in terms of actual height.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

The ordering rule covers entire subtrees
Insert and search along one justified path
Inorder traversal exposes sorted membership

The ordering rule covers entire subtrees

A binary search tree associates each node with a key and at most two children. Under this lesson’s set contract, every key in the left subtree is strictly smaller and every key in the right subtree strictly larger. Checking only immediate children is insufficient: a deeply misplaced key can satisfy its parent comparison while violating an ancestor bound. Define duplicate policy before insertion. The examples ignore repeated equal keys, representing unique membership rather than frequency. A multiset could store a count at each key, but that would be a different model with corresponding update rules.

Insert and search along one justified path

The first program descends according to comparisons until it finds an empty child or an existing key. At each step, the discarded subtree cannot contain the requested key under the invariant. Returning the root makes creation of an initially empty tree explicit. Search uses the same argument and terminates when it reaches either equality or an absent child. The code does not rebalance, so operation cost is O(h) for height h, not automatically O(log n). Inserting sorted distinct keys can produce a chain with linear height.

python Self-contained Python3 algorithm example using synthetic local data.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    node = root
    while True:
        if key == node.key:
            return root
        side = "left" if key < node.key else "right"
        child = getattr(node, side)
        if child is None:
            setattr(node, side, Node(key))
            return root
        node = child

def contains(root, key):
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

root = None
for key in [5, 2, 7, 2]:
    root = insert(root, key)
print(contains(root, 7))
print(contains(root, 8))

Expected output

True
False

Repeated2 does not create another node. Search follows one path whose length depends on the built tree.

Inorder traversal exposes sorted membership

The second program uses an explicit stack instead of Python recursion. It descends left while remembering ancestors, emits the nearest unfinished node, then explores its right subtree. The invariant is that the stack records the path of nodes whose left side is being completed before their own emission. Each node is pushed and popped once, so traversal takes O(n) time and O(h) stack space, excluding the returned O(n) output. For a valid strict search tree, the emitted keys are increasing. A traversal still runs on an ordinary binary tree, but sortedness then has no guarantee.

python Self-contained Python3 algorithm example using synthetic local data.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def inorder(root):
    output, stack = [], []
    current = root
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        output.append(current.key)
        current = current.right
    return output

root = Node(5, Node(2, Node(1), Node(3)), Node(7))
print(inorder(root))
print(inorder(None))

Expected output

[1, 2, 3, 5, 7]
[]

The explicit stack represents unfinished ancestors and avoids a recursion-depth dependency for this traversal.

Deletion must preserve more than one pointer

Deleting a leaf detaches one child link. Deleting a node with one child can reconnect its parent to that child. With two children, an implementation can replace the key with its inorder successor or predecessor and then delete the corresponding simpler node. Parent links, counts, heights, or subtree sizes must be updated if the representation maintains them. Do not advertise deletion as swapping arbitrary values until the picture looks plausible. The replacement must preserve all ancestor bounds and any external identity contract, especially when callers retain references to nodes rather than keys.

Balancing is an additional maintained invariant

AVL and other balanced search trees constrain height through specific update and rotation rules. A binary shape by itself does not supply those guarantees. A rotation preserves inorder key order while changing local ancestry, and augmented fields must follow the structural change. Learn the invariant and proof of a chosen balancing scheme before claiming logarithmic worst-case updates. For a static sorted dataset, an array with binary search can be simpler and more compact. Choose a tree when its full operation mix and ordering interface justify the extra mutation complexity, not merely because tree sounds efficient.

Validate global bounds and shape-sensitive cases

Test empty and singleton trees, repeated keys under the set policy, balanced insertion order, and sorted insertion order. Compare inorder output with sorted unique input and compare membership with a reference set. A validator should carry lower and upper ancestor bounds, not only compare parent-child pairs. Also verify that nodes are not shared or cyclic when the representation promises a tree. Tests can reveal a degenerate height without making it a correctness error for this unbalanced implementation; the error would be claiming a height guarantee the code never maintains.

Common errors and fixes

A deep key violates an ancestor while passing local checks

Why it happens: Validation compared only direct children.
How to fix it: Carry all relevant lower and upper bounds through validation.
Prevent it next time: Include a misplaced descendant two levels deep.

Search is claimed logarithmic for a chain

Why it happens: Binary branching was confused with maintained balance.
How to fix it: Express cost as O(h) and state whether h is bounded.
Prevent it next time: Test sorted insertion order and measure height.

Duplicate insertion changes a promised set

Why it happens: Duplicate semantics were undefined or inconsistent.
How to fix it: Choose ignore, replace, or count and apply it throughout operations.
Prevent it next time: Repeat the same key through build and membership tests.

Check your understanding

1. Why can a left grandchild greater than the root invalidate the tree?

Show worked solution

Every key in the root’s left subtree must be smaller than the root, regardless of its immediate parent. A local comparison can be satisfied while this ancestor condition fails. Validation needs inherited bounds or an equivalent global ordering argument.

2. Does replacing recursion with a stack make an unbalanced search logarithmic?