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 = dataFive Insertion Cases
Cases for inserting a node temp:
- case 1: the tree is empty, so
tempbecomes the root - case 2:
temp.data <= root.dataand the left child is empty, so attachtempas the left child - case 3:
temp.data > root.dataand the right child is empty, so attachtempas the right child - case 4:
temp.data <= root.dataand the left subtree is not empty, so insert recursively into the left subtree - case 5:
temp.data > root.dataand 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.