Binary Search Tree: The Art of Ordered Storage

A binary search tree, usually abbreviated as BST, is a tree data structure that stores values according to their ordering. Its central idea is simple: every node divides the values around it into two groups. Values smaller than the node belong in its left subtree, while values larger than the node belong in its right subtree.

This arrangement gives the tree a useful property. When searching for a value, we can compare the target with the current node and immediately choose a direction. If the target is smaller, the right subtree can be ignored. If the target is larger, the left subtree can be ignored. The tree does not need to examine every stored value.

The same ordering rule guides insertion and helps repair the tree during deletion. However, the performance of all three operations depends on the tree’s height. A compact tree can make operations efficient, while inserting already ordered values can stretch the tree into a chain. In that degenerate shape, search, insertion, and deletion can all require O(n) time.

This article explains the binary search tree from the structure upward. It introduces the ordering invariant, demonstrates search and insertion, breaks deletion into its three important cases, explains in-order traversal, and shows why insertion order has such a strong effect on complexity.

1. The basic shape of a binary search tree

A binary search tree consists of nodes connected in a hierarchy. Each node stores a value and can have up to two children:

A left child, which begins the smaller side of the node.
A right child, which begins the larger side of the node.

The top node is called the root. A node without children is a leaf. Every node below the root belongs to the left or right subtree of some ancestor.

Consider this tree:

The root is 8. Its left subtree contains 3, 1, and 6. Its right subtree contains 10 and 14. The value 1 is not just smaller than its parent, 3; it is also smaller than 8, the root. Similarly, 14 is larger than both 10 and 8.

The drawing shows the direct parent-child relationships, but the ordering rule applies to entire subtrees. A node acts as a divider for all of the values below it. At node 8, values on the left belong below 8 and values on the right belong above 8. At node 3, its own left subtree must contain values below 3, and its right subtree must contain values above 3.

Repeatedly applying this division creates an ordered hierarchy. The path from the root to any node also records the comparisons needed to locate that node.

2. The binary search tree invariant

An invariant is a condition that must remain true before and after an operation. The defining BST invariant is the ordering relationship between each node and its subtrees.

For a node containing value x, the usual distinct-value rule is:

all values in the left subtree < x < all values in the right subtree

This is stronger than saying that the immediate left child is smaller and the immediate right child is larger. For example, suppose a node contains 8, its right child contains 12, and that child’s left child contains 9. The value 9 is smaller than 12, but it is still correctly positioned because it is larger than 8 and belongs between 8 and 12.

The invariant is what makes directional search possible. At every node, a comparison eliminates an entire subtree:

If the target is smaller than the current value, it can only be in the left subtree.
If the target is larger than the current value, it can only be in the right subtree.
If the values are equal, the target has been found.

The distinct-value rule is common, but implementations may support duplicates. If duplicates are allowed, the implementation must define a consistent policy. Equal values might always go left, always go right, or be counted inside an existing node. The exact policy can vary, but it must be applied consistently during search, insertion, and deletion. Otherwise, the tree no longer has a predictable ordering rule.

Maintaining the invariant is the most important correctness requirement. If an insertion or deletion places a value on the wrong side of an ancestor, later searches may follow the wrong path and fail to find a value that is actually present.

3. Searching for a value

A BST search begins at the root. At each node, compare the target with the current value:

If the target equals the current value, the search succeeds.
If the target is smaller, move to the left child.
If the target is larger, move to the right child.
If the required child is empty, the target is not in the tree.

Using the example tree, search for 6:

The target 6 is smaller than 8, so move left to 3. It is larger than 3, so move right to 6. The values match, and the search succeeds.

The path is therefore:

8 -> 3 -> 6

Now search for 7. The first two decisions are the same: move from 8 to 3, then from 3 to 6. Since 7 is larger than 6, move right. If 6 has no right child, the search reaches an empty position and reports that 7 is absent.

A recursive version can be described like this:

search(node, target):
    if node is empty:
        return not found

    if target equals node.value:
        return found

    if target is smaller than node.value:
        return search(node.left, target)

    return search(node.right, target)

The same logic can be implemented iteratively with a loop. The important feature is not whether recursion or iteration is used. The essential operation is repeated comparison followed by a single directional choice.

The time complexity of search is O(h), where h is the height of the tree. Search visits only the nodes on one root-to-leaf path. In a compact tree, that path is short. In a skewed tree, the path can include nearly every node, making the operation O(n).

This height-based description is more accurate than simply saying that BST search is always fast. The ordering invariant enables guided search, but the tree’s shape determines how long the guided path becomes.

4. Inserting a new value

Insertion follows the same comparisons as search. Start at the root and follow the path that preserves the invariant. When the correct child position is empty, create the new node there.

Suppose the current tree contains 8, 3, 10, 1, and 6, and we insert 7:

The comparison path is:

7 is smaller than 8, so move left.
7 is larger than 3, so move right.
7 is larger than 6, so move right.
The right position below 6 is empty, so insert 7 there.

The new value is placed correctly not only relative to its parent, but also relative to all of its ancestors. It is smaller than 8, larger than 3, and larger than 6.

A recursive insertion has the following general form:

insert(node, value):
    if node is empty:
        return a new node containing value

    if value is smaller than node.value:
        node.left = insert(node.left, value)
    else if value is larger than node.value:
        node.right = insert(node.right, value)

    return node

In this version, an equal value is ignored. That is only one possible duplicate policy. A different implementation could insert equal values consistently on one side or maintain a count in the node. Whatever policy is selected must also be reflected in search and deletion.

Insertion takes O(h) time because it follows one path from the root to an empty position. A recursive implementation uses call-stack space proportional to the path length. An iterative implementation can avoid recursive calls, but it still has the same height-based running time.

One subtle point is that ordinary BST insertion does not automatically reorganize the tree. Once a value is inserted, it remains in that position unless a later operation removes or replaces it. As a result, the order in which values arrive can strongly influence the eventual shape.

5. Deleting a value

Deletion is more complicated than search or insertion because removing a node can leave a gap. The replacement must fit the surrounding ordering relationships. There are three structural cases: deleting a leaf, deleting a node with one child, and deleting a node with two children.

Case 1: deleting a leaf

A leaf has no children. Removing it simply changes the appropriate child reference of its parent to empty.

Start with:

If we delete 1, the result is:

No other nodes need to move. Since 1 had no children, there is no subtree that must be preserved or connected elsewhere.

The same reasoning applies when the leaf is the root. Removing the only node produces an empty tree.

Case 2: deleting a node with one child

If a node has exactly one child, that child can take the deleted node’s position. The parent connects directly to the child.

Consider this tree:

Node 6 has one child, 7. If 6 is deleted, its parent, node 3, can connect directly to 7:

This preserves the invariant. The value 7 is still greater than 3 and remains in the left subtree of 8, so its new position is valid.

If the node being deleted is the root and it has one child, the child becomes the new root. This is why update functions often return a subtree root rather than modifying only a local value. The root of a subtree may change during deletion.

Case 3: deleting a node with two children

The two-child case requires a replacement value that fits between the left and right subtrees. A common method uses the in-order successor: the smallest value in the node’s right subtree. Another equivalent method uses the in-order predecessor: the largest value in the node’s left subtree.

Suppose we delete 8 from this tree:

        8
       / \\
      3   10
     / \\    \\
    1   6    14

The smallest value in the right subtree of 8 is 10. We can copy 10 into the position formerly occupied by 8 and then remove the original node containing 10:

Why is 10 a valid replacement? Every value in the left subtree is smaller than 8 and therefore smaller than 10. The remaining values in the original right subtree are larger than or equal to 10 according to the chosen distinct-value arrangement. Once the original 10 is removed, the ordering remains valid.

To find the successor, move once to the right child and then follow left children as far as possible. The successor cannot have a left child, because it was selected as the smallest value in that right subtree. It may have a right child, so removing it becomes either the leaf case or the one-child case.

A general deletion procedure looks like this:

delete(node, target):
    if node is empty:
        return empty

    if target is smaller than node.value:
        node.left = delete(node.left, target)
    else if target is larger than node.value:
        node.right = delete(node.right, target)
    else:
        if node has no left child:
            return node.right
        if node has no right child:
            return node.left

        successor = smallest node in node.right
        node.value = successor.value
        node.right = delete(node.right, successor.value)

    return node

The code is schematic, and implementations may differ when nodes contain additional fields or when duplicates are supported. The structural reasoning is stable: first locate the target by comparisons, then repair the local structure without violating the global invariant.

Deletion takes O(h) time. The initial search follows one path. In the two-child case, finding and removing the successor follows another path whose length is bounded by the tree height. If the tree is degenerate, h can be O(n), so deletion can also become O(n).

6. In-order traversal and sorted output

An in-order traversal visits a node in this sequence:

Traverse the left subtree.
Visit the current node.
Traverse the right subtree.

For this tree:

        8
       / \\
      3   10
     / \\    \\
    1   6    14

in-order traversal produces:

1, 3, 6, 8, 10, 14

The output is sorted because the traversal order follows the invariant. The left subtree contributes smaller values, the current node contributes the dividing value, and the right subtree contributes larger values.

This gives a useful diagnostic property. For a distinct-value BST, an in-order traversal should produce values in increasing order. If the result is not sorted, either the tree does not satisfy the expected invariant or the traversal is incorrect.

In-order traversal takes O(n) time because it visits every node exactly once. This differs from search, which attempts to ignore entire subtrees. Traversal intentionally processes the complete structure, so its cost is based on the total number of nodes rather than only the height.

A recursive in-order traversal naturally mirrors the tree:

inOrder(node):
    if node is empty:
        return

    inOrder(node.left)
    visit(node.value)
    inOrder(node.right)

The traversal’s output remains sorted even when the tree is skewed. Shape affects the path depth and therefore the auxiliary call-stack depth, but it does not change the ordering of the values produced by a correct in-order traversal.

7. Tree height and operation complexity

The central performance measure for a BST is height. Height describes the longest root-to-node path, using the chosen convention for counting edges or levels. Since search, insertion, and deletion follow paths, their running time is expressed in terms of height.

Compare these two shapes containing the same number of values.

A relatively compact tree might look like this:

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

The nodes are distributed across both sides. A path from the root to a leaf is short compared with the total number of stored values.

A skewed tree might look like this:

This is still a valid BST. Every right child is larger than its parent, and the left subtrees are empty. However, the height grows with the number of nodes.

The resulting complexity statements are:

Search: O(h).
Insertion: O(h).
Deletion: O(h).
In-order traversal: O(n).

The first three operations are fast only when h is small relative to n. The BST invariant guarantees that a search can choose a direction, but it does not guarantee that the tree will be compact. Shape and ordering are related, but they are separate concerns.

8. O(n) degeneration from ordered insertion

The clearest way to create a degenerate BST is to insert values in already sorted order. Begin with an empty tree and insert:

1, 2, 3, 4, 5

The first value becomes the root:

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

1
 \\
  2

Insert 3. It is larger than 1 and larger than 2, so it continues to the right:

Insert 4:

Insert 5:

Each insertion must travel through every value already inserted. The tree has lost its useful branching shape and now behaves structurally like a one-directional linked list, although it still satisfies the BST invariant.

Descending insertion has the same effect in the opposite direction. Inserting 5, 4, 3, 2, 1 produces a chain of left children:

For n ordered insertions, the final height can be proportional to n. A search, insertion, or deletion may then visit O(n) nodes. This is the O(n) degeneration caused by ordered insertion.

Degeneration does not mean that the tree is incorrect. Every comparison still sends the operation in the correct direction. The problem is that the tree provides almost no branching. Each comparison advances only one step along a chain instead of excluding a large independent subtree.

9. Why shape matters so much

Suppose a tree contains values from 1 through 15. In a compact arrangement, the root divides the values into two substantial groups. Each later comparison divides one of those groups again. The search path is short because the possibilities shrink through several branching decisions.

In a chain, every node has at most one child. A comparison still gives the correct answer, but there is no alternative branch to discard. Searching for the largest value requires visiting every preceding node. Searching for a missing value beyond the largest also requires walking to the end before reaching an empty child position.

This is why it is misleading to describe every BST operation as automatically logarithmic. The operation follows the tree height. If the height is small, the operation is efficient. If the height approaches n, the operation becomes linear.

Ordered insertion repeatedly chooses the same side because every new value is larger than all previous values, or smaller than all previous values. The invariant remains intact, but the shape becomes increasingly unbalanced.

The tree therefore illustrates an important data-structure principle: an ordering invariant can make an operation possible without guaranteeing that the resulting structure has the best shape. Ordered storage provides navigable relationships, while the update history influences the cost of using those relationships.

10. A complete example of search, insertion, and deletion

Start with an empty tree and insert the values 8, 3, 10, 1, 6, and 14.

Insert 8:

Insert 3. Since 3 is smaller than 8, it becomes the left child:

  8
 /
3

Insert 10. Since 10 is larger than 8, it becomes the right child:

  8
 / \\
3  10

Insert 1. It is smaller than 8 and smaller than 3:

Insert 6. It is smaller than 8 but larger than 3:

Insert 14. It is larger than 8 and larger than 10:

    8
   / \\
  3   10
 / \\    \\
1   6    14

Search for 6 follows the path 8 -> 3 -> 6. Search for 14 follows 8 -> 10 -> 14. Search for 5 follows 8 -> 3 -> 6, then checks the appropriate empty child position.

Now delete 3. Node 3 has two children, 1 and 6. Its in-order successor is the smallest value in its right subtree, which is 6. Replace 3 with 6 and remove the original 6:

    8
   / \\
  6   10
 /      \\
1        14

The resulting tree remains valid. The left subtree of 8 contains only values smaller than 8. Within that subtree, 1 is smaller than 6. The right subtree of 8 contains values larger than 8.

This example shows that search, insertion, and deletion are variations of comparison-guided movement. Search stops when it finds a match or reaches an empty position. Insertion stops at an empty position and creates a node. Deletion first locates a node, then repairs the structure according to its number of children.

11. Practical implementation concerns

Empty trees

An empty tree has no root. Searching it immediately reports that the target is absent. Inserting into it creates the root. Deleting from it has no effect because there is no node to remove.

The root can change

Deletion can change the root of the whole tree or of a subtree. Removing a root leaf produces an empty tree. Removing a root with one child promotes that child. Removing a root with two children replaces its value or position using a successor or predecessor.

Recursive functions should therefore return the updated subtree root. A call such as node.left = delete(node.left, target) is important because the left child reference may need to point to a different node after deletion.

Missing values

A search or deletion may reach an empty child position. This is the normal stopping condition for a missing value. Search reports failure, while deletion leaves the tree unchanged.

Duplicate values

Duplicate handling must be explicit. An implementation may ignore duplicate insertions, store a count, or place equal values consistently on one side. The chosen policy affects comparison conditions and deletion behavior. A tree that sometimes sends equals left and sometimes sends them right can become difficult to search reliably.

Updating references

When a leaf is removed, a parent reference becomes empty. When a one-child node is removed, the parent reference skips over the deleted node. When a two-child node is replaced, the original successor or predecessor must also be removed. Forgetting to update one of these references can disconnect a subtree or leave duplicate values in the structure.

Checking the invariant

After an update, inspect more than the immediate children. A node can appear locally correct while violating an ancestor’s boundary. A value in the right subtree of 8 must remain greater than 8 even if its immediate parent is larger than it. The invariant applies to complete subtrees and all ancestor relationships.

12. A practical method for tracing operations

When working through an example by hand, write the comparison path before drawing the final structure. For insertion, continue until reaching an empty position. For search, continue until finding the target or reaching an empty position. For deletion, first locate the target and then classify its children.

For example, inserting 7 into the tree rooted at 8 produces this trace:

-> left because 7 < 8
-> right because 7 > 3
-> right because 7 > 6
empty -> insert here

The trace explains both the operation and the resulting shape.

For deletion, use this checklist:

Find the target using ordinary BST comparisons.
Count its children.
If it has no children, remove it.
If it has one child, connect that child to the parent.
If it has two children, select the successor or predecessor.
Remove the replacement from its original position.
Verify the ordering invariant around the repaired subtree.

For complexity, ask how long the path can become. A short path means the operation is efficient relative to the number of stored nodes. A chain means the path may include almost every node. Thinking in terms of height avoids the incorrect assumption that every binary search tree has the same performance.

13. Correctness and performance are different questions

A binary search tree can be correct but slow. Correctness means that the invariant is maintained and that operations return the right results. Performance depends on the number of nodes an operation must traverse.

The ordered-insertion example makes this distinction clear. After inserting 1, 2, 3, 4, and 5, the resulting tree is valid. A search for 4 compares 4 with 1, then 2, then 3, and finally 4. No comparison is wrong. The search is slow only because the structure offers no shorter path.

When reviewing an implementation, separate these concerns:

If a search returns the wrong answer, check comparisons, child links, and the ordering invariant.
If a search returns the right answer but takes too long, inspect the tree’s height and construction order.
If deletion produces incorrect later searches, check replacement selection and reference updates.
If traversal is not sorted, check either the invariant or the traversal order.

Deletion may preserve correctness while leaving the tree tall or skewed. Selecting a valid successor maintains the ordering rule, but it does not automatically make the overall structure compact. Correct update logic and favorable shape are separate goals.

14. The central lesson of ordered storage

The appeal of a binary search tree comes from putting order into the structure itself. Instead of storing values arbitrarily and scanning them one by one, the tree uses each node as both a stored value and a decision point.

That decision-making structure has two sides:

When branches are distributed across the tree, comparisons quickly narrow the possible location.
When updates repeatedly choose the same branch, the structure becomes a long path and loses much of its practical advantage.

The BST therefore demonstrates a broader lesson about data structures. An invariant can make efficient navigation possible, but the shape created by updates determines how effective that navigation will be. The ordering rule is necessary for guided search; it is not sufficient to guarantee a small height.

A binary search tree should be understood as the interaction between values and structure. Every comparison chooses a direction, every insertion extends a path, and every deletion repairs a local gap while preserving global order. When the shape remains compact, ordered storage becomes efficient navigation. When already ordered insertion stretches the tree into a chain, the same invariant remains correct but the operation cost degenerates to O(n).

15. Summary checklist

When working with a binary search tree, remember the following:

Each node has at most one left child and one right child.
The left subtree contains smaller values according to the chosen ordering policy.
The right subtree contains larger values according to that policy.
Search compares the target with the current node and chooses one subtree.
Insertion follows the same path and places a value at an empty position.
Deletion must handle leaf, one-child, and two-child cases.
A two-child deletion can use the smallest value in the right subtree or the largest value in the left subtree as a replacement.
In-order traversal visits the values in sorted order.
Search, insertion, and deletion take O(h), where h is the tree height.
In-order traversal takes O(n) because it visits every node.
Inserting already ordered values can make the height O(n).
In the resulting degenerate shape, search, insertion, and deletion can all require O(n) time.
A valid ordering invariant does not automatically produce a balanced tree.
Duplicate handling must be defined and applied consistently.
Root and child references may change during deletion.

The key is to reason about both the rule and the shape. The invariant explains why each comparison can eliminate a subtree. The height explains how many comparisons remain. Together, these ideas provide the practical foundation for understanding binary search trees and the O(n) degeneration caused by ordered insertion.

1. The basic shape of a binary search tree​

2. The binary search tree invariant​

3. Searching for a value​

4. Inserting a new value​

5. Deleting a value​

Case 1: deleting a leaf​

Case 2: deleting a node with one child​

Case 3: deleting a node with two children​

6. In-order traversal and sorted output​

7. Tree height and operation complexity​

8. O(n) degeneration from ordered insertion​

9. Why shape matters so much​

10. A complete example of search, insertion, and deletion​

11. Practical implementation concerns​

Empty trees​

The root can change​

Missing values​

Duplicate values​

Updating references​

Checking the invariant​

12. A practical method for tracing operations​

13. Correctness and performance are different questions​

14. The central lesson of ordered storage​

15. Summary checklist​