Why isn't a plain binary search tree O(log n)?

A strong answer

A strong candidate frames Why isn't a plain binary search tree O(log n)? around the exact memory layout, compiler semantics, and hardware execution model covered in Why binary search trees degrade. Explain how insertion order determines a binary search tree's height, which inputs break it, and what balancing must guarantee.

A binary search tree keeps every key in the left subtree of a node smaller than the node's key, and every key in the right subtree larger. Search, insert, delete, finding the minimum, finding the next larger key: each of them follows one path down from the root, choosing left or right at every node. So every operation costs O(h), where h is the height of the tree.

When the tree is well shaped, h is about log₂ n: twenty levels for a million keys, thirty for a billion. That is the promise of a search tree, the same as binary search on a sorted array, but with fast insertion and deletion. The trouble is that nothing in the plain insertion algorithm keeps that promise. A new key always becomes a leaf wherever its search ends, so the shape of the tree is decided entirely by the order in which keys arrive.

In a production interview, always connect the specification rule to its concrete runtime consequence: state what lives on the stack versus the heap or static storage segment, how the compiler or operating system validates alignments, lifetimes, and error codes, and what happens under adversarial or boundary inputs (such as zero-length buffers, integer overflow, concurrent mutation, or partial I/O). Backing your explanation with a small trace of register/memory state transitions immediately separates senior systems engineers from candidates who only memorized syntax.

What the interviewer is listening for

• Mastery of core invariant: Explain why every binary search tree operation costs O(height), and how insertion order sets the height.
• Mastery of core invariant: Recognize the inputs that make a plain tree degenerate, and the expected height under random order.
• Mastery of core invariant: Rebuild a balanced tree from sorted data, and state what a self-balancing tree must guarantee.
• Hardware and ABI awareness: Explaining how sizes, alignments, calling conventions, or kernel boundaries behave on real 64-bit targets rather than relying on implementation-defined assumptions.
• Defensive engineering: Naming the exact compiler flags (-Wall -Wextra -Werror), static analyzers, or runtime sanitizers (-fsanitize=address,undefined,thread) that verify correctness in CI.

Common mistakes

• Explaining only surface syntax without tracing the underlying memory addresses, ownership lifetime, or kernel/user-space state transitions.
• Assuming undefined behavior (such as signed overflow, uninitialized reads, strict-aliasing violations, or dangling pointers) will "just work" because it passed an unoptimized -O0 debug build.
• Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.