Binary search trees

1 · Learn and explore

Study this example, identify inputs and outputs, then trace the key variables. Run and adapt it in Python 3.

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

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

def contains(root, target):
    while root is not None:
        if target == root.value: return True
        root = root.left if target < root.value else root.right
    return False

root = None
for n in (8, 3, 10, 1, 6): root=insert(root,n)

2 · Independent programming challenge

Insert and search for integer values in a binary search tree. Download the starter, design your solution, and add tests before revealing the answer.

Download starter + solution ZIP ↓

Stretch task: investigate time/space complexity or data validation, then write an evaluation of your approach.

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

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

def contains(root, target):
    while root is not None:
        if target == root.value: return True
        root = root.left if target < root.value else root.right
    return False

root = None
for n in (8, 3, 10, 1, 6): root=insert(root,n)
assert contains(root,6) and not contains(root,9)
print('BST tests passed')

3 · Debug and explain

Change one boundary condition in the starter or reference program. Predict which test fails, then repair it and document why.

Concept check: What is the worst-case search time for an unbalanced binary search tree?

4 · Assess your learning

Describe the algorithm or design in your own words; include a normal test, a boundary test and an invalid input. Compare your answers with the reference solution and record one improvement.

Progress is stored only in this browser.