4.7 Insertion |

Inserting new nodes into a binary search tree is easy. To start out, we work the same way as in a search, traversing the tree from the top down, as if we were searching for the item that we're inserting. If we find one, the item is already in the tree, and we need not insert it again. But if the new item is not in the tree, eventually we “fall off” the bottom of the tree. At this point we graft the new item as a child of the node that we last examined.

An example is in order. Consider this binary search tree:

Suppose that we wish to insert a new item, 7, into the tree. 7 is greater than 5, so examine 5's right child, 8. 7 is less than 8, so examine 8's left child, 6. 7 is greater than 6, but 6 has no right child. So, make 7 the right child of 6:

We cast this in a form compatible with the abstract description as follows:

33. <BST item insertion function 33> =void**bst_probe(structbst_table*tree,void*item)

{structbst_node*p, *q; /* Current node in search and its parent. */intdir; /* Side ofqon whichpis located. */structbst_node*n; /* Newly inserted node. */assert(tree!=NULL&&item!=NULL);for(q=NULL,p=tree->bst_root;p!=NULL;q=p,p=p->bst_link[dir])

{intcmp=tree->bst_compare(item,p->bst_data,tree->bst_param);if(cmp== 0)return&p->bst_data;dir=cmp> 0; }n=tree->bst_alloc->libavl_malloc(tree->bst_alloc,sizeof*p);if(n==NULL)returnNULL;tree->bst_count++;n->bst_link[0] =n->bst_link[1] =NULL;n->bst_data=item;if(q!=NULL)q->bst_link[dir] =n;else

tree->bst_root=n;return&n->bst_data; }

This code is included in 30.

**See also:**
[Knuth 1998b], algorithm 6.2.2T;
[Cormen 1990], section 13.3;
[Bentley 2000], section 13.3;
[Sedgewick 1998], program 12.7.

**Exercises:**

**1.** Explain the expression *p* = (**struct** **bst_node** *) &*tree*->*bst_root*.
Suggest an alternative.
[answer]

**2.** Rewrite *bst_probe*() to use only a single local variable of type
**struct** **bst_node** **.
[answer]

**3.** Suppose we want to make a new copy of an existing binary search tree,
preserving the original tree's shape, by inserting items into a new,
currently empty tree. What constraints are there on the order of item
insertion?
[answer]

**4.** Write a function that calls a provided **bst_item_func** for each node
in a provided BST in an order suitable for reproducing the original
BST, as discussed in Exercise 3.
[answer]