Binary Search Trees: Smaller Left, Larger Right—and the List-Shaped Worst Case

A binary search tree, usually abbreviated as BST, stores values in a branching structure governed by one ordering rule:

• Values smaller than a node belong in its left subtree.
• Values larger than a node belong in its right subtree.

That rule gives each comparison a purpose. Instead of scanning every stored value, a search compares its target with the current node and chooses one direction. When the tree has a reasonably compact shape, the number of comparisons grows much more slowly than the number of stored values. This is why binary search tree search is commonly described as $O(\log n)$ on average for a tree containing $n$ values.

There is an important qualification, however: a normal binary search tree does not automatically remain short or balanced. The ordering rule controls where values belong, but it does not by itself control how tall the tree becomes. If values arrive in sorted order, every new value can be placed on the same side of the previous value. The tree then becomes a chain that looks more like a linked list than a branching tree. Search, insertion, and deletion can then require $O(n)$ work.

This article explains the operations represented by the animation—search, insertion, and deletion—and connects each operation to the shape of the tree. The central idea is simple:

where $h$ is the tree's height. If $h$ is near $\log n$, the operation is efficient. If $h$ is near $n$, the operation is linear.

1. The basic shape of a binary search tree​

A tree consists of nodes connected by parent-child relationships. In a binary tree, each node has at most two child positions: a left child and a right child. A binary search tree adds an ordering invariant to that shape.

An invariant is a condition that should remain true before and after an operation. For a BST, the usual invariant is:

• Every value in a node's left subtree is smaller than the node's value.
• Every value in a node's right subtree is larger than the node's value.

Consider this example:

        8
      /   \\
     3     12
    / \\    / \\
   1   5  10  15

The immediate children of 8 are 3 and 12. The value 3 is smaller than 8, so it appears on the left. The value 12 is larger than 8, so it appears on the right.

The rule is recursive, not limited to immediate children. The values 1, 3, and 5 are all in the left subtree of 8, and all are smaller than 8. The values 10, 12, and 15 are all in the right subtree of 8, and all are larger than 8.

The same relationship applies below every node. In the subtree rooted at 3, the value 1 is smaller and the value 5 is larger. In the subtree rooted at 12, the value 10 is smaller and the value 15 is larger.

This recursive ordering is what makes directed search possible. A BST is not merely a collection of values arranged in a branching picture. Each node provides information about an entire region below it. Once a comparison tells us that the target must be on one side, the other subtree can be ignored.

The root and subtrees​

The topmost node is the root. Every node below a particular node forms a subtree. For example, the subtree rooted at 3 contains 3, 1, and 5. The subtree rooted at 12 contains 12, 10, and 15.

A useful way to reason about the invariant is to think of each node as having a range of acceptable values. At the root, the range may be unrestricted. Once we move left from 8, the acceptable values must be less than 8. If we then move right from 3, the value must be greater than 3 but still less than 8. This range-based view helps detect errors that are not visible from a node's immediate children alone.

For example, a node might be larger than its parent while still violating the ordering imposed by an earlier ancestor. Correct BST reasoning therefore applies to entire subtrees, not just to individual parent-child pairs.

2. Why a search follows one path​

Suppose the target is 10 in the example tree. A search starts at the root, 8:

1. Compare 10 with 8.
2. Because 10 is larger, move to the right child, 12.
3. Compare 10 with 12.
4. Because 10 is smaller, move to the left child, 10.
5. The target is found.

The path is:

8 -> 12 -> 10

At the root, the search does not inspect the entire left subtree. Every value there is smaller than 8, so that subtree cannot contain 10. After moving to 12, the search can ignore the right subtree of 12, because every value there is larger than 12 and therefore cannot equal 10.

A search for a missing value follows the same decision process. Search for 11:

1. 11 is larger than 8, so move right.
2. 11 is smaller than 12, so move left.
3. The left child of 12 is 10.
4. 11 is larger than 10, so move right.
5. If that right child is empty, the search fails.

A failed search ends when the required child position is empty. It does not need to visit every remaining node.

The decision process can be summarized as follows:

start at the root
while the current node exists:
    if the target equals the current value:
        report success
    else if the target is smaller:
        move to the left child
    else:
        move to the right child
report failure

The running time is determined by the length of the path. If the tree has height $h$, a search examines at most a root-to-leaf path of that height, so its cost is $O(h)$.

For a relatively compact tree, the height is often near $\log n$:

The approximation describes favorable or average behavior, not a guarantee for every possible tree. The smaller-left, larger-right rule enables directed search, but the height determines how many directed decisions must be made.

3. Insertion follows the same path​

Insertion uses the same comparisons as search. Instead of stopping when the target is found or when an empty position proves that the target is absent, insertion stops at an empty child position and places the new node there.

Start with the following tree:

        8
      /   \\
     3     12
    / \\    / \\
   1   5  10  15

Insert 6:

1. Compare 6 with 8. It is smaller, so move left to 3.
2. Compare 6 with 3. It is larger, so move right to 5.
3. Compare 6 with 5. It is larger, so move right.
4. The right child of 5 is empty, so place 6 there.

The resulting tree is:

        8
      /   \\
     3     12
    / \\    / \\
   1   5  10  15
        \\
         6

The new value is in the left subtree of 8, but it is larger than both 3 and 5. Its location is therefore consistent with every relevant ancestor.

Insertion has the same asymptotic path cost as search. With height $h$, it takes $O(h)$ time. For a tree with average height near $\log n$, insertion is commonly described as average $O(\log n)$. For a highly skewed tree, it can become $O(n)$.

Handling equal values​

A complete implementation also needs a policy for duplicates. The basic rule says that smaller values go left and larger values go right, but it does not specify where equal values belong. Possible policies include:

• Reject duplicate values.
• Store a count of equal values in one node.
• Always place equal values on one consistently chosen side.

The specific policy is a design choice, but search and insertion must use the same rule. If insertion sends equal values one way while search looks for them another way, the ordering information becomes unreliable.

Why insertion order matters​

Insertion does not normally reorganize existing nodes. It follows the current shape and attaches the new node at the first suitable empty position. Consequently, the order in which values arrive influences the future height of the tree.

An insertion order that repeatedly chooses both sides can create a branching structure. An increasing order repeatedly chooses right, while a decreasing order repeatedly chooses left. The same ordering invariant is maintained in both cases, but the performance can be dramatically different.

4. Deletion is more structural than search or insertion​

Deletion begins like a search: follow comparisons until the target node is found or an empty position proves that it is absent. Once the node is found, the repair depends on how many children it has.

There are three standard structural cases:

1. The node is a leaf with no children.
2. The node has exactly one child.
3. The node has two children.

The first two cases can be repaired by changing one parent link. The third case requires an ordered replacement so that both remaining subtrees still fit around the replacement value.

Case 1: deleting a leaf​

A leaf has no children. Consider:

    8
   /
  3

If 3 is deleted, its parent simply loses its left child:

  8

No other subtree needs to move. Because the removed node was at the end of a path, the ordering invariant remains intact.

The root can also be a leaf. If a tree contains only one node and that node is deleted, the tree becomes empty.

Case 2: deleting a node with one child​

Consider:

    8
   /
  3
   \\
    5

If 3 is deleted, its only child, 5, can take its position:

    8
   /
  5

The parent bypasses the deleted node and points directly to its child. The same idea works when the one child is on the left.

This shortcut is valid because the child's entire subtree already belongs in the deleted node's position. In the example, 5 is greater than 3 but still smaller than 8, so it remains a valid member of 8's left subtree.

Case 3: deleting a node with two children​

Consider the following tree:

        8
      /   \\
     3     12
    / \\    / \\
   1   5  10  15

Suppose 8 is deleted. Its left subtree contains values smaller than 8, while its right subtree contains values larger than 8. Replacing 8 with an arbitrary value could break the ordering relationship between those subtrees.

A common solution is to use the smallest value in the right subtree. In this example, that value is 10. It is larger than every value in the left subtree and is the first value in the right-side ordering.

The conceptual steps are:

1. Find the smallest node in the right subtree.
2. Use that value in the deleted node's position.
3. Remove the original occurrence of the replacement from the right subtree.
4. Repair that original position.

The result can be represented as:

        10
      /    \\
     3      12
    / \\      \\
   1   5      15

The original 10 was the leftmost node in the right subtree, so it had no left child. Its original position therefore requires no complicated two-sided rearrangement. More generally, the replacement position has at most one child along the relevant search path.

Another standard approach is to use the largest value in the left subtree. In this tree, that value would be 5. Both choices work because each is a boundary value that fits between the remaining left and right regions.

Deletion spends time finding the target and, in the two-child case, finding a replacement. These are downward path operations, so the usual height-based bound is $O(h)$. A compact tree gives average behavior associated with $O(\log n)$; a chain can make deletion $O(n)$.

5. Tree height controls the work​

The height of a tree is the length of its longest downward path from the root to a node. Some definitions count nodes rather than edges, but the difference is only a constant and does not change the asymptotic complexity.

Consider a compact shape:

          8
       /     \\
      4       12
     / \\     /  \\
    2   6   10  14

Paths through this tree are short. Each level provides additional possible positions, so a well-shaped binary tree can hold many nodes while keeping root-to-leaf paths relatively small.

The logarithm appears because branching allows the number of possible positions to grow quickly as height increases. In an idealized filled binary tree of height $h$, the number of positions through all levels is:

The geometric sum is:

Thus, a tree with height near $h$ can contain on the order of $2^h$ positions in a filled shape. Reversing that relationship gives height near $\log n$.

This calculation explains why a compact binary tree can support logarithmic path lengths. It is not a guarantee for every ordinary BST, because a BST may be sparse or skewed. The useful general statement is:

Then:

The tree's shape is therefore not a visual detail. It is the main factor controlling the amount of work.

6. How sorted insertion creates a list​

The clearest worst case occurs when values are inserted in increasing order. Start with 1:

1

Insert 2. Since 2 is larger than 1, it becomes the right child:

1
 \\
  2

Insert 3. It is larger than 1, so move right. It is also larger than 2, so move right again:

1
 \\
  2
   \\
    3

Insert 4:

1
 \\
  2
   \\
    3
     \\
      4

Each new value extends the same rightward path. The structure still satisfies the BST invariant, but the branching advantage has disappeared. It behaves like a singly linked list ordered from smallest to largest.

Decreasing insertion produces the mirror image:

    4
   /
  3
 /
2
/
1

For an increasing sequence of $n$ values, searching for the largest value may require visiting every node. The path length is proportional to $n$:

The recurrence reflects the structure. After the first node, the remaining values occupy one subtree with one fewer node, and each level adds a constant amount of comparison work.

This is why O(log n) on average must not be interpreted as O(log n) for every tree. The ordering invariant tells us which direction is correct, but a skewed tree can require many consecutive decisions in that same direction.

The same values, different shapes​

The values 1, 2, 3, 4, and 5 can form a chain if inserted in increasing order:

1
 \\
  2
   \\
    3
     \\
      4
       \\
        5

A different insertion order can create a more compact structure:

      3
    /   \\
   1     4
    \\
     2    \\
           5

This second tree is not perfectly balanced, but its paths are shorter than those of the chain. The values are identical; only their arrangement differs.

This demonstrates an important distinction:

• The ordering invariant determines which side a value belongs on.
• The insertion history influences the height and shape.

A binary search tree can preserve its ordering invariant while losing most of its performance advantage.

7. Complexity summary​

Let $n$ be the number of nodes and $h$ be the height. For the operations discussed here, height is the most direct measure of work.

The table separates the precise height-based statement from the common average-case description. Each operation is fundamentally $O(h)$. If the height is near $\log n$, the operation is logarithmic. If the height is near $n$, the operation is linear.

The word average is important. It describes typical behavior for a suitable distribution of shapes or insertion orders. It is not a promise that every input sequence creates logarithmic height. An increasing or decreasing sequence can produce a linear-height chain immediately.

The tree's node storage is proportional to the number of values, $O(n)$. A recursive implementation may use temporary call-stack space proportional to the height, $O(h)$. An iterative implementation can follow the path with a current-node reference and use constant additional traversal state, while the nodes themselves still require $O(n)$ storage.

These resource descriptions do not change the main lesson: for ordinary BST operations, the height is the performance variable to inspect.

8. Why every update must preserve the invariant​

A search is correct only when the ordering information can be trusted. If insertion places a value on the wrong side, a later search may discard the subtree containing that value. If deletion reconnects subtrees incorrectly, the same failure can occur.

Suppose a node has value 8. A value of 4 belongs somewhere in its left subtree, while a value of 12 belongs somewhere in its right subtree. If deleting 8 replaces it with an arbitrary value from one region, the two subtrees may no longer fit around the replacement.

A correct two-child deletion selects a boundary value, such as:

• The smallest value in the right subtree, or
• The largest value in the left subtree.

These values are safe because they are adjacent to the deleted value in the relevant ordering. They can occupy the deleted node's position without reversing the relationship between the two remaining regions.

A useful way to check an update is to examine three levels of correctness:

1. Link correctness: the parent points to the intended child or replacement.
2. Subtree correctness: every remaining descendant still belongs in the correct local region.
3. Global ordering correctness: for every node, all values in its left subtree are smaller and all values in its right subtree are larger, according to the duplicate policy.

Checking only immediate children is not enough. A deeper descendant might violate an ancestor's range even if it appears to be on the correct side of its direct parent. The recursive invariant must remain true throughout the entire affected subtree.

9. Understanding a visual animation​

An animation of BST operations makes the comparison path visible. To follow it, ask a few questions at each step:

• Which node is currently being compared with the target?
• Is the target smaller or larger than that node?
• Which child is selected as a result?
• Is the operation looking for a value, adding a new endpoint, or reconnecting existing nodes?
• After the update, do all left subtrees still contain smaller values and all right subtrees still contain larger values?

For search, the key visual feature is the single highlighted path. Nodes outside that path are not inspected one by one because comparisons have already ruled them out.

For insertion, watch the path continue until an empty child position is reached. The new node is attached at that endpoint. Existing nodes generally remain where they were, which is why insertion history can gradually create a skewed shape.

For deletion, identify the structural case. A leaf disappears. A node with one child is bypassed. A node with two children is replaced by an ordered value, and the replacement's original position is repaired.

Finally, observe what happens after many sorted insertions. If every new value extends the same side, the tree becomes a vertical chain. That visual transformation explains the move from average logarithmic behavior to linear worst-case behavior more clearly than complexity notation alone.

10. Practical implementation checklist​

When implementing a binary search tree, the following checklist helps keep the operations consistent:

1. Define the ordering rule clearly: smaller values go left and larger values go right.
2. Decide how equal values are handled before implementing search and insertion.
3. Make search use exactly the same comparison policy as insertion.
4. Insert only at an empty position reached by the comparison path.
5. For deletion, distinguish leaf, one-child, and two-child nodes.
6. For two-child deletion, choose an ordered replacement from a subtree boundary.
7. Reconnect the replacement's original position correctly.
8. Test an empty tree, a one-node tree, and a chain.
9. Test targets at the root, at a leaf, between existing values, and outside the stored range.
10. Inspect or reason about height instead of assuming that every BST is logarithmic.

Small structural tests are especially useful. A tree containing one node tests root deletion. A three-node tree can expose all child configurations. A sorted insertion sequence exposes the list-shaped worst case. A mixed insertion sequence demonstrates how branching can shorten paths.

It is also useful to test unsuccessful operations. Searching for a value below the minimum should end at a left-side empty position, while searching for a value above the maximum should end at a right-side empty position. Deleting an absent value should leave the structure unchanged.

When testing deletion, check not only that the requested value disappears but also that searches for all remaining values still succeed. This verifies that reconnection preserved the invariant rather than merely removing one visible node.

11. Common misunderstandings​

A BST is not automatically balanced​

The smaller-left, larger-right rule specifies ordering, not height. A tree can satisfy the rule while being a long chain.

Average $O(\log n)$ is not a universal guarantee​

The logarithmic statement describes average behavior for a suitable shape or insertion pattern. Sorted insertion can produce height $O(n)$ and make path-based operations linear.

A binary tree is not necessarily a binary search tree​

A binary tree only limits each node to at most two children. It does not necessarily impose a value ordering. The search advantage comes from the BST invariant, not merely from having two child positions.

Deletion is not always just removing a pointer​

Removing a leaf is simple, but a node with children needs reconnection. A two-child deletion must preserve the ordering of both subtrees.

More nodes do not alone determine the cost​

Two trees can contain the same number of nodes and have very different heights. The number of comparisons is controlled primarily by the path length from the root.

The root is not permanently special​

The root is simply the current starting point. Deleting the root may leave the tree empty, replace it with its only child, or replace its value with an ordered predecessor or successor when it has two children. The same invariant applies after the root changes.

12. The central trade-off​

A BST provides a useful compromise between an entirely unsorted collection and a permanently ordered linear arrangement. It stores values in a branching structure, and each comparison selects a direction. When the shape is short, this produces efficient average search, insertion, and deletion.

The trade-off is that ordinary BST insertion does not necessarily control the shape. The structure can preserve its ordering invariant while losing its height advantage. Sorted input is the clearest example: every comparison chooses the same direction, so branching disappears and the tree becomes list-like.

The complete performance story can be summarized as:

Then consider the two important height regimes:

The comparisons determine the path. The path determines the work. The insertion history helps determine the path's length.

13. Final takeaways​

A binary search tree is organized by the smaller-left, larger-right invariant. That invariant lets a search discard one subtree at every comparison and follow a single downward path.

Insertion uses the same path logic, continuing until it finds an empty position. Deletion begins with a search and then repairs the tree according to whether the target has zero, one, or two children.

For a tree of height $h$, these operations take $O(h)$ time. When the tree has a favorable height near $\log n$, their average behavior is described as $O(\log n)$. But the BST rule does not by itself prevent a poor shape. Increasing or decreasing sorted inserts can create a chain with height near $n$, turning searches and updates into $O(n)$ operations.

When analyzing or implementing a BST, do not ask only whether the values are ordered. Also inspect the shape. A branching tree makes the comparison rule useful; a list-shaped tree preserves the rule but loses most of its performance advantage.

The most important habit is therefore to connect the abstract complexity to the visible structure. If each comparison sends the operation toward one of several short branches, logarithmic behavior is plausible. If every comparison sends it farther down one long chain, the operation is effectively walking a list. The invariant explains correctness, while the height explains performance.