Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Why a BST

To find someone by height later, pick a middle value (say 165 cm) and send shorter people to the left and taller people to the right, then repeat on each side. A binary search tree stores data with this partition idea, using the Binary Search Tree Property:

  • every value in the left subtree of is
  • every value in the right subtree of is

Insertion and deletion change the tree, but always in a way that keeps this property true.

Building a BST

Inserting in that order: becomes the root, values at most go left and values greater than go right, and the same rule repeats at each node.

Node Set-Up

Each node holds left, data and right. A new node starts with both children None.

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

Five Insertion Cases

Cases for inserting a node temp:

  • case 1: the tree is empty, so temp becomes the root
  • case 2: temp.data <= root.data and the left child is empty, so attach temp as the left child
  • case 3: temp.data > root.data and the right child is empty, so attach temp as the right child
  • case 4: temp.data <= root.data and the left subtree is not empty, so insert recursively into the left subtree
  • case 5: temp.data > root.data and the right subtree is not empty, so insert recursively into the right subtree

Full Insertion Algorithm

def BSTinsert(root, val):
    temp = Node(val)
    if root is None:                     # case 1
        return temp
    BSTinsert_recurs(root, temp)
    return root
 
def BSTinsert_recurs(root, temp):
    if temp.data <= root.data:
        if root.left is None:            # case 2
            root.left = temp
        else:                            # case 4
            BSTinsert_recurs(root.left, temp)
    else:
        if root.right is None:           # case 3
            root.right = temp
        else:                            # case 5
            BSTinsert_recurs(root.right, temp)

Search and Cost

Searching for follows the same path: start at the root and go left if node value, right otherwise, until is found or the path ends at None.

Each step goes one level down, so insert and search take time proportional to the height . This is for a balanced tree but in the worst case, e.g. inserting already sorted data makes a single chain.

Exam tip: when writing BST code, always handle the two edge cases, an empty tree and a tree with one node.