Describe a binary search tree, perform insertion, search and in-order traversal, and explain how balance affects complexity

What this dot point is asking

SEAB wants you to describe a binary search tree (BST), perform insertion, search and in-order traversal, and explain how the tree's balance affects its complexity. The central idea is that the BST ordering property lets you discard half the remaining nodes at each step - giving $O(\log n)$ operations when the tree is balanced, but only then.

The answer

The ordering property

A binary search tree is a binary tree where each node has up to two children and obeys the rule:

• every key in a node's left subtree is smaller than the node's key, and
• every key in its right subtree is larger.

This holds at every node, so the tree encodes a sorted ordering implicitly.

Searching

Searching mirrors binary search. Start at the root; if the target equals the node, you are done; if smaller, go left; if larger, go right; if you reach null, it is absent:

def search(node, target):
    if node is None or node.key == target:
        return node
    if target < node.key:
        return search(node.left, target)
    return search(node.right, target)

Each comparison discards one subtree, so search takes time proportional to the tree's height.

Insertion

Insertion follows the same path until it finds an empty (null) spot, then attaches the new node there:

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

In-order traversal gives sorted output

An in-order traversal visits the left subtree, then the node, then the right subtree. Because left holds smaller keys and right holds larger, this always emits the keys in ascending order:

def in_order(node):
    if node is not None:
        in_order(node.left)
        print(node.key)
        in_order(node.right)

Balance and complexity

The cost of every operation is the tree's height $h$:

• A balanced tree has height about $\log_2 n$, so search, insert and delete are $O(\log n)$.
• An unbalanced tree - for example one built by inserting already-sorted keys, so every node goes the same way - degenerates into a "stick" of height $n$, making operations $O(n)$, no better than a list.

Self-balancing trees keep the height logarithmic automatically; without balancing, insertion order can ruin performance.

Examples in context

Example 1. An ordered symbol table. A compiler storing variable names so it can both look them up quickly and list them alphabetically uses a balanced BST: search is $O(\log n)$, and a single in-order traversal prints every name in sorted order for a symbol dump - two needs met by one structure.

Example 2. Range queries. A BST of timestamps lets a log viewer find all events between two times efficiently: navigate to the lower bound, then traverse in order until the upper bound. The sorted structure makes range scans natural in a way a hash table cannot, since hashing destroys order.

Try this

Q1. What does an in-order traversal of a binary search tree produce? [1 mark]

• Cue. The keys in ascending sorted order, because left subtrees hold smaller keys and right subtrees larger.

Q2. Inserting the keys 1, 2, 3, 4, 5 in that order into an empty BST gives what shape, and what search complexity? [2 marks]

• Cue. A right-leaning stick of height 5 (each key larger than the last), giving $O(n)$ search - the degenerate worst case.

Q3. Why is a balanced binary search tree preferred over an unbalanced one? [2 marks]

• Cue. Its height stays near $\log_2 n$, keeping search, insert and delete at $O(\log n)$ rather than degrading to $O(n)$.