Binary search trees and a pathological insertion order

A binary search tree can become a linked chain when keys arrive in sorted order. Its lookup cost depends on the tree’s height, so the familiar O(log n) search bound needs a balancing guarantee or an explicit assumption about the input. For a student comparing tree structures, inserting the same seven keys in two orders makes that qualification visible.

Use distinct integer keys one through seven. Inserting 1, 2, 3, 4, 5, 6, 7 puts every new key to the right of the previous one. Inserting 4, 2, 6, 1, 3, 5, 7 creates a full tree with four at the root. Both trees obey the binary-search-tree ordering rule, but their paths have different lengths.

The ordering rule leaves the shape unconstrained

At each node, every key in the left subtree must be smaller than the node’s key, and every key in the right subtree must be larger. This is a subtree-wide requirement. Checking only the immediate children can miss a misplaced descendant.

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 search(root, key):
    visits = 0
    while root is not None:
        visits += 1
        if key == root.key:
            return True, visits
        root = root.left if key < root.key else root.right
    return False, visits

chain = balanced = None
for key in range(1, 8):
    chain = insert(chain, key)
for key in [4, 2, 6, 1, 3, 5, 7]:
    balanced = insert(balanced, key)
assert search(chain, 7) == (True, 7)
assert search(balanced, 7) == (True, 3)
assert search(chain, 8) == (False, 7)
assert search(balanced, 8) == (False, 3)

The duplicate policy is to keep one copy of each key. A dictionary-like tree would update the existing key’s value instead. Allowing equal keys on one side is another possible policy, but it changes the ordering invariant and can create long duplicate chains unless the structure addresses that case.

The counter records visited nodes. A visit can perform both an equality test and an ordering test, so it is not a count of every primitive comparison. Keeping the unit explicit avoids comparing unlike instrumentation later.

View full-size image ↗

Here height counts edges: a leaf has height zero. The chain’s height is six and the full tree’s height is two. A longest successful root-to-leaf search visits height plus one nodes. An unsuccessful search may follow a similarly long path to an absent child.

Search correctness does not imply short paths

At a node with key k, a requested key smaller than k cannot occur in the right subtree under the invariant. Search can discard that subtree and descend left. The symmetric argument handles a larger key. If the key equals k, the node supplies the answer; if the selected child is absent, no valid location remains.

That proves correctness regardless of shape. It does not prove that each step discards half of the remaining nodes. In the chain, descending right discards only the current node and an empty left subtree. In the full tree, the subtrees are similar in size, so a path becomes much shorter.

A tree with height h supports search and this simple insertion in O(h + 1) node visits. In the worst case, h = n - 1, giving O(n) per operation. Inserting a sorted sequence into an initially empty tree costs 0 + 1 + ... + (n - 1) existing-node visits, or Θ(n²) total construction work.

State how balance is obtained

The second insertion order constructs a balanced tree for this example, but the implementation does not preserve balance after future insertions. Appending many keys larger than seven creates a new rightward chain. A favorable starting shape is not a maintained invariant.

AVL and red-black trees perform local rotations and metadata updates to bound height after changes. A randomized search tree uses a different mechanism and gives probabilistic guarantees. Open Data Structures’ unbalanced-tree chapter separates the basic ordering behavior from the later balancing techniques.

If insertion order is a uniformly random permutation of distinct keys, expected search-tree behavior is much better than the sorted-order case. That assumption can support expected logarithmic costs for standard operations, but application timestamps, incrementing IDs, or already sorted imports are plainly not uniform random permutations. Write down the actual source of ordering before relying on that model.

For static sorted keys, a sorted array with binary search may be simpler and use less pointer storage. A tree becomes attractive when ordered updates, range iteration, predecessor, or successor operations are part of the workload. Princeton’s binary-search-tree material describes these ordered symbol-table operations.

Test the whole subtree invariant

A validator can pass lower and upper key bounds recursively. Every node in a left subtree inherits the parent’s upper bound; every node in a right subtree inherits its lower bound. For example, a key twelve placed as the right child of node five inside the left subtree of root ten violates the root’s bound even though twelve is greater than its immediate parent.

Tests should include sorted insertion, reverse-sorted insertion, duplicate keys, and missing keys beyond both ends. Verify an in-order traversal returns the distinct inserted keys in ascending order. Check the node-visit counter separately to observe shape without turning a timing measurement into a complexity claim.

The iterative implementation avoids using the language call stack for a long chain. A recursive insert or traversal on the same unbalanced input may exceed a recursion limit before running out of ordinary heap memory. The tree shape therefore affects both the operation count and the safety of an implementation that mirrors paths with recursive calls.

Turn inherited bounds into an executable check

A whole-tree validator can carry the allowable key interval with every pending node. The interval is open at both ends because this tree stores distinct integer keys. A left child inherits its parent’s lower bound and gets the parent’s key as its upper bound; a right child receives the symmetric interval.

The implementation below also tracks node identities. A tree requires each reachable node to have one position: a cycle or a shared child is a structural failure even before discussing search costs. Using an explicit pending list avoids recursive calls on the long chains that this lesson deliberately creates.

def valid_bst(root):
    pending = [(root, None, None)]
    seen = set()
    while pending:
        node, low, high = pending.pop()
        if node is None:
            continue
        if id(node) in seen:
            return False
        seen.add(id(node))
        if low is not None and node.key <= low:
            return False
        if high is not None and node.key >= high:
            return False
        pending.append((node.right, node.key, high))
        pending.append((node.left, low, node.key))
    return True

assert valid_bst(chain)
assert valid_bst(balanced)
assert valid_bst(None)

misplaced = Node(10)
misplaced.left = Node(5)
misplaced.left.right = Node(12)
assert misplaced.left.key < misplaced.key
assert misplaced.left.right.key > misplaced.left.key
assert not valid_bst(misplaced)

cycle = Node(1)
cycle.right = cycle
assert not valid_bst(cycle)

The two local comparisons in the invalid example both pass: five is below ten and twelve is above five. The inherited interval at twelve is (5, 10), however, so twelve violates the upper bound from the root. No sequence of correct search decisions can compensate for that misplaced descendant. A search for twelve would go right at ten and miss the node hidden on the left.

View full-size image ↗

The validator accepts both the seven-node chain and the balanced tree because both satisfy ordering and ownership. That is intentional: it checks a valid binary search tree, not an AVL or red-black invariant. A slow valid tree and a fast-looking invalid tree are different failures, and tests should identify them separately.

On a proper tree of n nodes, this check visits each node once. The identity set uses O(n) storage, and the pending traversal holds at most O(h + 1) entries for tree height h. Total extra storage is therefore O(n). Removing the identity set would reduce memory for trusted tree structures but would remove its explicit protection against repeated node identities. The None bounds are sentinels for unbounded integer intervals; this particular validator does not accept None as a key.

As an exercise, validate a long sorted-insertion chain, then move a descendant across an inherited bound while leaving its immediate parent relation correct. Check that the former passes and the latter fails. Finally count visits for every successful search in the two seven-key trees: the chain totals twenty-eight visits, while the balanced tree totals seventeen. Uniformly choosing a stored key would therefore give means four and seventeen-sevenths respectively. Those are workload-specific means, distinct from the maximum path lengths in the first figure.