A BST stores keys so every left descendant is < the node and every right descendant is >. Search and insert follow one child. Average Θ(log n) if the tree is balanced; a sorted insert sequence becomes a list — Θ(n).

Goal

Insert cities, search, and print an inorder walk (sorted).

Insert and search

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

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

def search(node, key, steps=0):
    if node is None:
        return False, steps
    steps += 1
    if key == node.key:
        return True, steps
    if key < node.key:
        return search(node.left, key, steps)
    return search(node.right, key, steps)

root = None
for city in ["Nakuru", "Nairobi", "Mombasa", "Kisumu", "Eldoret"]:
    root = insert(root, city)
print(search(root, "Kisumu"))
print(search(root, "Kericho"))

Inorder

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

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    return node

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.key] + inorder(node.right)

root = None
for city in ["Nakuru", "Nairobi", "Mombasa", "Kisumu", "Eldoret"]:
    root = insert(root, city)
print(inorder(root))

Inorder of a BST is sorted. That is the invariant.

Pitfall

Inserting already-sorted keys (A, B, C, D) builds a stick. Then search is linear. Balanced trees (AVL, red-black) fix that; this course stops at the unbalanced BST so the risk is visible.