Binary Search Trees (aka Ordered Binary Tree)

A binary search tree is a binary tree that may be empty or non-empty. It must satisfy the following properties:

1. Each element is distinct

2. The elements in the left subtree of the root are less than the root

3. The elements in the right subtree of the root are greater than the root

4. The left and right subtrees of the root are also binary search trees

Binary search trees produce infix, postfix, and prefix notations with the same properties as a regular binary tree

The infix is the easiest to derive. Why?

Assume that a particular ORDERED Binary Search tree exists which produces the following POSTORDER traversal sequence with 24 nodes:

  6   15   10   20   35   27   80  100   89  79  52  140  170  153  101
190  251  210  350  375  400  519  307  172

Write down the corresponding INORDER and PREORDER traversal sequence of this binary tree.

Processing a Binary Search Tree

The way that a binary search tree is set up makes processing of the tree easy to implement.

Searching

Starting at the root of the tree, compare the data field against the item being searched for:

• if the item < data field, go left

• if the item > data field, go right

repeat the process until you reach a null pointer or find the item.

ptr = root
found = false

while (ptr is not null AND !found)
  if search value < ptr->data
    ptr = ptr->leftChild

  else if search value > ptr->data
    ptr = ptr->rightChild

  else
    found = true
endwhile

Insertion

Starting at the root of the tree, compare the data field against the item to insert:

• if the item < data field, go left

• if the item > data field, go right

repeat the process until you reach a null pointer or find a duplicate item. If you find a duplicate, do not insert. If find a null pointer, insert.

ptr = root
parentPtr = null
found = false

while (ptr is not null AND !found)
  parentPtr = ptr
  
  if insert value < ptr->data
    ptr = ptr->leftChild

  else if insert value > ptr->data
    ptr = ptr->rightChild

  else
    found = true
endwhile

if insert value is found
  duplicate item in tree

else
  if parentPtr is null
    insert as root of tree

  else if item < parentPtr->data
    insert as parentPtr's left child

  else
    insert as parentPtr's right child
  endif
endif

Deletion

This is the hardest of the processes to implement.

There are three cases that need to be considered when deleting a node from a binary search tree:

1. the node to delete is a leaf

2. the node to delete has one child

3. the node to delete has two children

Case 1: make the appropriate pointer of the nodes parent null

Case 2: make the appropriate pointer of the nodes parent point to the child

Case 3: the node to be deleted will have its data field replaced by the data field of a chosen node and then the chosen node will be deleted. There are two ways to choose a node:

1. Inorder successor - smallest value in the node's right subtree

2. Inorder predecessor - largest value in the node's left subtree

After the successor/predecessor has been copied, it can be treated as either a case 1 or 2 node.

Pseudocode using INORDER SUCCESSOR logic

ptr = root
parentPtr = null
found = false

while (ptr is not null AND !found)
  
  if delete value < ptr->data
    parentPtr = ptr
    ptr = ptr->leftChild

  else if delete value > ptr->data
    parentPtr = ptr
    ptr = ptr->rightChild

  else
    found = true
endwhile

if delete value is not found
  nothing to delete

else
  if ptr has two children           // case 3
    ptrSucc = ptr->right           //find the inorder successor
    parentPtr = ptr

    while ptrSucc has a left child
      parentPtr = ptrSucc
      ptrSucc = ptrSucc->left
    endwhile
    
    ptr->data = ptrSucc->data      //node to delete now has succ. value
    ptr = ptrSucc
  endif

/* below this -- case 1 and 2 are combined */

  subtreePtr = ptr->left
  if subtreePtr is null
    subtreePtr = ptr->right
  endif
  
  if parentPtr is null              //tree consists of root only
    root = subtree

  else if parentPtr->left is ptr    //if left child is being deleted,
    parentPtr->left = subtreePtr    //then subtree is new left child

  else                              //right child is being deleted
    parentPtr->right = subtreePtr   //new right child is subtree
  endif
  
  delete ptr
endif



Logic for finding INORDER PREDECESSOR

ptrPred = ptr->left
parentPtr = ptr

while ptrPred has a right child
  parentPtr = ptrPred
  ptrPred = ptrPred->right
endwhile

ptr->data = ptrPred->data      //node to delete now has pred. value
ptr = ptrPred