Binary Search Tree – Insertion, Introduction

Binary search trees (BSTs) are very simple to understand. We start with a root node with value x, where the left subtree of x contains nodes with values < x
and the right subtree contains nodes whose values are ¸ x. Each node follows the same rules with respect to nodes in their left and right subtrees. BSTs are of interest because they have operations which are favourably fast: insertion, look up, and deletion can all be done in O(log n) time. It is important to note that the O(log n) times for these operations can only be attained if the BST is reasonably balanced; for a tree data structure with self balancing properties see AVL tree de¯ned in x7).

In the following examples you can assume, unless used as a parameter alias that root is a reference to the root node of the tree.

Insertion

As mentioned previously insertion is an O(log n) operation provided that the tree is moderately balanced.
1) algorithm Insert(value)
2) Pre: value has passed custom type checks for type T
3) Post: value has been placed in the correct location in the tree
4) if root = ; 5) root à node(value)
6) else
7) InsertNode(root, value)
8) end if
9) end Insert

1) algorithm InsertNode(current, value)
2) Pre: current is the node to start from
3) Post: value has been placed in the correct location in the tree
4) if value < current.Value
5) if current.Left = ; 6) current.Left à node(value)
7) else
8) InsertNode(current.Left, value)
9) end if
10) else
11) if current.Right = ; 12) current.Right à node(value)
13) else
14) InsertNode(current.Right, value)
15) end if
16) end if
17) end InsertNode

The insertion algorithm is split for a good reason. The ¯rst algorithm (non- recursive) checks a very core base case – whether or not the tree is empty. If
the tree is empty then we simply create our root node and ¯nish. In all other cases we invoke the recursive InsertNode algorithm which simply guides us to
the ¯rst appropriate place in the tree to put value. Note that at each stage we perform a binary chop: we either choose to recurse into the left subtree or the
right by comparing the new value with that of the current node. For any totally ordered type, no value can simultaneously satisfy the conditions to place it in
both subtrees.