Binary Search Trees (BSTs) often feel like something you only encounter in a college whiteboard interview, but they're incredibly useful when you need a data structure that stays sorted while allowing for fast lookups. If you're dealing with a dataset that's constantly changing but needs to be searchable in logarithmic time, a BST is your best friend.

To keep this concrete, let's build a simple Employee Directory. Imagine we have thousands of employees, each with a unique ID number. We want to be able to insert new hires and find existing employees without scanning the entire list every single time.

The anatomy of a single node

Before we build the tree itself, we need the building block: the Node. In a BST, every node is essentially a small container that holds a value and two pointers—one for the left child (smaller values) and one for the right child (larger values). I like to keep this class lean; it doesn't need any logic, just storage.

class EmployeeNode:
    def __init__(self, emp_id, name):
        self.emp_id = emp_id
        self.name = name
        self.left = None
        self.right = None

Wiring up the insertion logic

Now we need a Directory class to manage these nodes. The key to a BST is the rule: smaller to the left, larger to the right. I usually implement this recursively because it mirrors the structure of the tree itself. It's cleaner and easier to reason about than a while-loop with a bunch of temporary tracking variables.

class EmployeeDirectory:
    def __init__(self):
        self.root = None

    def insert(self, emp_id, name):
        if self.root is None:
            self.root = EmployeeNode(emp_id, name)
        else:
            self._insert_recursive(self.root, emp_id, name)

    def _insert_recursive(self, current, emp_id, name):
        if emp_id < current.emp_id:
            if current.left is None:
                current.left = EmployeeNode(emp_id, name)
            else:
                self._insert_recursive(current.left, emp_id, name)
        elif emp_id > current.emp_id:
            if current.right is None:
                current.right = EmployeeNode(emp_id, name)
            else:
                self._insert_recursive(current.right, emp_id, name)

The "None" trap I almost fell into

When I first wrote a version of this, I tried to make the _insert_recursive method return the node itself to make the code more compact. I wrote something like current.left = self._insert_recursive(current.left, ...). The problem? I forgot to actually return the node at the base case.

I spent twenty minutes debugging why my tree was suddenly becoming a forest of None values. It's a classic Python mistake: if a function doesn't explicitly return something, it returns None. By assigning the result of a return-less function back to current.left, I was effectively deleting my own tree as I built it. That's why in the version above, I chose to handle the assignment explicitly when the child is None. It's slightly more verbose, but much harder to break.

Retrieving an employee by ID

Searching is where the BST really shines. Instead of checking every employee, we can discard half the remaining tree with every single comparison. It's the same logic as the insertion: go left if the ID is smaller, right if it's larger.

    def search(self, emp_id):
        return self._search_recursive(self.root, emp_id)

    def _search_recursive(self, current, emp_id):
        if current is None:
            return None  # Not found
        
        if emp_id == current.emp_id:
            return current.name
        
        if emp_id < current.emp_id:
            return self._search_recursive(current.left, emp_id)
        
        return self._search_recursive(current.right, emp_id)

Proving it works with a sorted dump

One of the coolest properties of a BST is that if you visit the nodes in a specific order (Left, Root, Right), you get the data back in perfectly sorted order. This is called an in-order traversal. I always implement this as a sanity check to make sure my insertion logic didn't accidentally flip a sign somewhere.

    def list_all_employees(self, current, result=None):
        if result is None:
            result = []
        
        if current:
            self.list_all_employees(current.left, result)
            result.append(f"{current.emp_id}: {current.name}")
            self.list_all_employees(current.right, result)
        
        return result

# Quick test drive
dir = EmployeeDirectory()
dir.insert(105, "Alice")
dir.insert(80, "Bob")
dir.insert(120, "Charlie")
dir.insert(70, "David")

print(dir.list_all_employees(dir.root)) 
# Expected: ['70: David', '80: Bob', '105: Alice', '120: Charlie']

📋 Practical Task

Build a Student Grade Lookup BST

Now it's your turn. You need to implement a Binary Search Tree that stores student records. Each record should consist of a student_id (the key) and a grade (the value).

Requirements:

• Create a StudentNode class to hold the ID and grade.
• Create a GradeBook class with an add_student(student_id, grade) method.
• Implement a get_grade(student_id) method that returns the grade if the student exists, or a message saying "Student not found" if they don't.
• Implement a get_all_grades_sorted() method that uses in-order traversal to return a list of all student IDs and grades in ascending order of their IDs.

Test Case: Add students with IDs 50 (Grade: A), 30 (Grade: B), 70 (Grade: C), 20 (Grade: D), and 40 (Grade: F). Your sorted list should return them in the order: 20, 30, 40, 50, 70.