Intermediate · INTERACTIVE LESSON

Binary search tree operations

Follow key comparisons and child links through search, insertion and deletion in an unbalanced binary search tree.

The interactive player is loading. If it does not appear, you can still read the explanation below.

THE IDEA BEHIND THE STEPS

How it works

A binary search tree keeps every left-subtree key smaller than its node and every right-subtree key larger. Search compares the requested key at each node and follows only the possible child. Insertion follows the same path and attaches a new leaf at the first null link. This lesson uses set semantics: inserting an existing value leaves the tree unchanged. Searching or deleting an absent value is an explained no-op.

Deletion has three cases. A leaf is removed. A node with one child is replaced by that child. A node with two children is replaced by its inorder successor, the smallest node in its right subtree. The successor is detached from its old location, its right child fills that link, and the successor takes the deleted node's place. The engine applies this structural update atomically so every displayed tree remains ordered and connected. Node IDs belong to successful insertion operations (n1, n2, and so on), not values; a transplanted successor keeps its ID and value.

Enter a JSON object with operations, an ordered list of 0–32 insert, search or delete operations, each with an integer value from -999 to 999. Start with an empty tree. At most 15 live nodes are supported; inserting a new key when full is an explained no-op, and later operations continue. Duplicate insertion remains a duplicate no-op even when full. Presets include empty, balanced-looking, skewed, deletion cases, absent/duplicate keys and capacity overflow. Editing hides stale results until valid input is applied.

Comparisons count one three-way key comparison at each visited search-path node. Following successor links does not compare keys. Link updates count changed root or existing child pointers, excluding initialization of a new leaf and discarded pointers of removed nodes. Completed attempts include successful operations and no-ops. Animation steps, validation, invariant checks and layout work are not algorithm comparisons.

For a pointer-based tree with constant-time key comparison, each operation takes O(h) time where h is the height in nodes; an empty tree takes O(1). A balanced shape has h=O(log n), but this tree never rebalances, and a skew can have h=n, giving O(n) worst-case operations. An immediate match can take O(1). The tree stores O(n) nodes; iterative traversal uses O(1) auxiliary algorithm space. The simulator also builds lookup/layout data and copies replay snapshots: these costs, input validation, O(n) post-operation invariant checks, counter bookkeeping and rendering are separate from the conceptual algorithm bounds. Playback speed is not a benchmark. Reduced motion preserves every state without movement.