All subjects · Computer Science · WCP04 Advanced Practical Programming and Problem-solving

Implementing a binary search tree

Edexcel IAL Computer Science · WCP04 Advanced Practical Programming and Problem-solving

A binary search tree (BST) keeps data in order as it is added, so searching usually halves the remaining data at every step. The Unit 4 sample paper asks for exactly this: a node class, an insert procedure that takes a node as a parameter, and building a tree from a list.

Practise this in the app: instant marking and a fix for every mistake. Free, no email needed to start.

Practise this lesson

The structure

Each node holds data and two references, left and right (None when there is no child). The first node is the root; nodes with no children are leaves.
The rule: everything in a node's left subtree is smaller than the node; everything in its right subtree is larger. Strings compare alphabetically, so a tree of names is in alphabetical order.
The tree is reached through the root reference only.

Insert and find

To insert, compare with the current node and go left or right until you reach an empty child reference, then attach a new node there. Recursion expresses this neatly. Find follows the same path and stops when it meets the target or falls off the tree.

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

def insert(node, value):
    if value < node.data:
        if node.left is None:
            node.left = Node(value)
        else:
            insert(node.left, value)
    elif value > node.data:
        if node.right is None:
            node.right = Node(value)
        else:
            insert(node.right, value)
    # equal values are ignored: no duplicates

def find(node, target):
    while node is not None:
        if target == node.data:
            return True
        node = node.left if target < node.data else node.right
    return False

def build(values):
    root = Node(values[0])
    for v in values[1:]:
        insert(root, v)
    return root

Building a tree from a list

The first value becomes the root and the rest are inserted in order, so the order of insertion decides the shape.

# Node, insert, find and build as above

root = build(["mango", "apple", "pear", "kiwi", "banana", "plum"])
print(root.data, root.left.data, root.right.data, root.left.right.data)
print(find(root, "kiwi"), find(root, "grape"))

Output:

mango apple pear kiwi
True False

Inserting already-sorted data produces a 'stick' where every node has only a right child, and searching becomes as slow as a linked list. A balanced tree with n nodes has a height of about log2 n.

Exam tips

Read the question for whether insert should be a method of a tree class or a procedure taking a node, and follow the given names.
Handle the empty tree (root is None) and decide what happens with duplicates.
Your code must work for a list of any length, not just the sample data.

Worked example

Insert 50, 30, 70, 20, 40, 60 into an empty BST. Which nodes are compared when searching for 40?

50 is the root. 30 < 50 goes left; 70 goes right. 20 goes left of 30; 40 goes right of 30; 60 goes left of 70.
Search for 40: 40 < 50, go left to 30; 40 > 30, go right to 40: found.
Check: True True

Answer: Three nodes are visited: 50, 30, 40.

Key idea: Node(data, left, right); smaller values go left, larger go right; insert by walking to an empty reference; find follows the same path; first value is the root and insertion order sets the shape; sorted input gives an unbalanced tree.

Check yourself

The Node, insert, find and build code from the lesson is included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root r = build([8, 3, 10, 1, 6, 14]) print(r.left.data, r.left.right.data, r.right.right.data) ```
Show answer
3 6 14. 3 < 8 goes left; 6 is less than 8 but more than 3, so right of 3; 14 goes right of 10. Output: `3 6 14`
The Node, insert, find and build code from the lesson is included in the code below. How many nodes are visited when searching for 50? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root r = build([40, 20, 60, 10, 30, 50, 70]) count = 0 node = r while node is not None and node.data != 50: count = count + 1 node = node.left if 50 < node.data else node.right print(count + 1) ```
Show answer
3. 50 > 40 goes right to 60; 50 < 60 goes left to 50. That is `3` nodes visited.
The Node, insert, find and build code from the lesson is included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root r = build(["lime", "fig", "date", "plum"]) print(r.left.left.data, r.right.data) ```
Show answer
date plum. fig < lime goes left; date < lime and date < fig goes left of fig; plum > lime goes right. Output: `date plum`
The Node, insert, find and build code from the lesson is included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root def height(node): if node is None: return 0 return 1 + max(height(node.left), height(node.right)) print(height(build([1, 2, 3, 4, 5]))) ```
Show answer
5. Sorted input makes every node a right child, so the tree is a chain of `5` levels.
The Node, insert, find and build code from the lesson is included in the code below. What does this print? ```python class Node: def __init__(self, data): self.data = data self.left = None self.right = None def insert(node, value): if value < node.data: if node.left is None: node.left = Node(value) else: insert(node.left, value) elif value > node.data: if node.right is None: node.right = Node(value) else: insert(node.right, value) # equal values are ignored: no duplicates def find(node, target): while node is not None: if target == node.data: return True node = node.left if target < node.data else node.right return False def build(values): root = Node(values[0]) for v in values[1:]: insert(root, v) return root r = build([5, 5, 2, 5]) print(r.left.data, r.right) ```
Show answer
2 None. Equal values match neither < nor >, so duplicates are ignored: only 2 is added, as the left child. Output: `2 None`
In a binary search tree, where are all values smaller than the root found?
- In the root's right subtree
- Only in leaf nodes
- In the root's left subtree
- Directly below the root, in either subtree
Show answer
In the root's left subtree. The BST rule: left subtree smaller, right subtree larger, at every node.
Why is inserting already-sorted data into a BST a problem?
- Every node gets only a right child, so searching takes as long as a linear search
- The insert procedure crashes
- The values are stored in reverse order
- The root becomes the largest value
Show answer
Every node gets only a right child, so searching takes as long as a linear search. The tree degenerates into a chain with height n.
Which line safely starts a tree when the variable root may be None?
- `insert(None, value)`
- `if root is None: root = Node(value)` before calling insert(root, value) for later values
- `root.data = value`
- `root = None.left`
Show answer
`if root is None: root = Node(value)` before calling insert(root, value) for later values. The insert procedure assumes a real node to compare with, so the empty tree must be handled first.

Practise with instant feedback

Sources

Last updated 8 November 2026. Spotted a mistake? Tell us.