Binary trees and binary search trees

Binary trees and BSTs

A tree is a connected graph with no cycles, with one root node. In a binary tree each node has at most two children (left and right). Nodes with no children are leaves.

A binary search tree (BST) adds a rule: for every node, everything in the left subtree is smaller and everything in the right subtree is larger (or equal, by a stated convention).

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

Insert and search

Insert: start at the root; go left if the new value is smaller, right if larger; repeat until you reach an empty position, and attach the node there.

Search: same path; stop when found, or report not found on reaching an empty position.

Inserting 50, 30, 70, 20, 40, 60, 80, 35 in that order gives root 50; 30 and 70 as its children; 20 and 40 under 30; 60 and 80 under 70; 35 as the left child of 40. Height = 4 levels.

A balanced tree is searched in O(log n); a tree built from already sorted data becomes a chain and degrades to O(n).

Traversals

Remember them by when the node is visited relative to its subtrees:

• Pre-order: node, left, right. Copies a tree or gives prefix expressions.
• In-order: left, node, right. Outputs a BST in ascending order.
• Post-order: left, right, node. Deletes a tree safely or gives postfix (reverse Polish).

Delete

• Leaf: remove it (set the parent's pointer to None).
• One child: link the parent directly to that child.
• Two children: replace the node's value with its in-order successor (the smallest value in its right subtree), then delete that successor node from the right subtree.

Benefits of a BST: fast search, insert and delete when balanced; data kept in order. Drawbacks: unbalanced trees are slow; more complex to code; pointers use memory.

Worked example

Search the tree built from 50, 30, 70, 20, 40, 60, 80, 35 for 35.

1. Compare with 50: 35 is smaller, go left.
2. Compare with 30: 35 is larger, go right.
3. Compare with 40: 35 is smaller, go left.
4. Compare with 35: found.

Answer: Found after 4 comparisons: 50, 30, 40, 35.

Check yourself

1. Values 40, 25, 60, 10, 30, 50 are inserted in that order into an empty BST. Give the pre-order traversal.
   Show answer

   40, 25, 10, 30, 60, 50. Node, left, right: 40, 25, 10, 30, 60, 50.

2. For the same tree (40, 25, 60, 10, 30, 50 inserted in order), give the post-order traversal.
   Show answer

   10, 30, 25, 50, 60, 40. Left, right, node: 10, 30, 25, 50, 60, 40.

3. Which traversal of a binary search tree outputs the values in ascending order?
   • In-order
   • Pre-order
   • Post-order
   • Breadth-first
   Show answer

   In-order. Left subtree (smaller), node, right subtree (larger).

4. How many comparisons are needed to find 60 in the tree built from 50, 30, 70, 20, 40, 60, 80, 35?
   Show answer

   3. 50 (go right), 70 (go left), 60 (found): 3.

5. Values 10, 20, 30, 40, 50 are inserted in that order into an empty BST. How many levels does the tree have?
   Show answer

   5. Each value is larger than the last, so every node is a right child: a chain of 5 levels.

6. In the tree built from 50, 30, 70, 20, 40, 60, 80, 35, node 30 (children 20 and 40) is deleted using the in-order successor. Which value replaces 30?
   • 40
   • 20
   • 50
   • 35
   Show answer

   35. The in-order successor is the smallest value in 30's right subtree: 40's left child, 35.

7. Pink, Green, Azure, Red, Purple, Yellow is the output of a traversal of a BST with root Pink. Which traversal starts with the root?
   • In-order
   • Pre-order
   • Post-order
   • Reverse in-order
   Show answer

   Pre-order. Pre-order visits the node first, so the root is output first.

8. Why can a BST built from data that is already sorted be slow to search?
   • Every node goes to the same side, so the tree becomes a chain and search becomes linear
   • Sorted data cannot be stored in a tree
   • The root is always deleted
   • In-order traversal no longer works
   Show answer

   Every node goes to the same side, so the tree becomes a chain and search becomes linear. Height n instead of about log n.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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