Search and Insert in One Descent

Compare, go left or right, and insert where the descent falls off the tree.

Searching a binary search tree and inserting into one follow the same path: compare with a node, then go left if the key is smaller or right if it is larger, until the key is found or the next link is empty. This card covers both operations, step by step, on a small tree, and shows why a new key always ends up as a leaf.

The tree holds 1, 2, 3, 4, 6 and 7, inserted in the order 4, 2, 6, 1, 3, 7. Node 6 has a right child, 7, and an empty left link, drawn as null. Each step below shows the line a run printed for it.

The starting tree, with an empty link to the left of 6

4, root
- 2
  - 1
  - 3
- 6
  - null, empty left link
  - 7

Inserting 5, searching for 7 and 8, and inserting 6 again, one comparison at a time

Insert 5: compare with 4

5 is larger than 4, so 5 can only belong in the right subtree. The left subtree, with 1, 2 and 3, is never looked at again.

text

insert 5: 5 > 4, go right

Insert 5: compare with 6

5 is smaller than 6, so it belongs to the left of 6. That link is empty, so the search has fallen off the tree at the one place 5 fits, and 5 becomes the left child of 6. No existing node moves.

text

insert 5: 5 < 6, left is empty, 5 becomes its left child
after insert: 4(2(1, 3), 6(5, 7))

Search for 7

7 is larger than 4, so go right; 7 is larger than 6, so go right again; the next node holds 7, so the search ends there. Three comparisons, one per level.

text

search 7: 7 > 4, go right
search 7: 7 > 6, go right
search 7: equal to 7, found

Search for 8

8 takes the same path as 7, then goes right from 7 and meets an empty link. Every key larger than 7 would have to be there, so 8 is not in the tree. Inserting 8 would follow this same path and attach 8 as the right child of 7.

text

search 8: 8 > 4, go right
search 8: 8 > 6, go right
search 8: 8 > 7, go right
search 8: fell off the tree, not found

Insert 6 a second time

6 is larger than 4, then equal to 6. The ordering rule says smaller goes left and larger goes right, and says nothing about an equal key, so the tree needs a rule of its own. This one ignores the duplicate, which suits a set of distinct keys.

text

insert 6: 6 > 4, go right
insert 6: equal to 6, already present, ignored

An insert is a failed search followed by one new link. The search ends at an empty link, and that is the only place the new key can go without breaking the order, so a new key always becomes a leaf. Nothing above it is rearranged, which is why an insert costs the same O(h) as a search, where h is the tree's height.

Duplicates need a rule that every operation shares. Three are common: ignore a repeated key, as the run did; keep a count in the node; or always send an equal key to the same side, say the right. A search must then follow the same rule, or it will look on the wrong side for a key that is there.

← → move through sections and cards