6.13.  Inserting an Element in a BST

Adding a new element x to a BST is straightforward. The following recursive algorithm sketches the idea:

Basis: If the tree is empty, replace T by a new node and place x at that node. If the tree is not empty and its root has element x, then x is already in the tree and we do nothing.

Induction: If the tree is not empty and does not have x at its root, then insert x into the left subtree if x is less than the element at the root, or insert x into the right subtree if x is greater than the element at the root.

The algorithm as a Nassi Shneidermann diagram:

Procedure Insert_Element(node new_root, lable x):

Examples:

• Draw a BST.

  1.   Input: 9 3 5 1 9 0
  2.   Input: 8 4 6 2 12 9 14
  3.   Input: 5 -5 5 -1 3 0 2 1
  4.   Input: 1 2 3 4 5 6 7
  5.   Input: 7 6 5 4 3 2 1
  

Last modified 22/May/97