Think of a family tree: one person at the top, each link pointing downward to children, then grandchildren, with no person appearing twice. Computer scientists borrowed this exact shape — calling it a tree data structure — and it turns up everywhere from file systems to the way decisions branch inside a programme.
What are the key terms for trees?
A tree is made of nodes (the circles or boxes holding data) connected by edges (the lines or arrows between them). The vocabulary below is essential for exam answers:
| Term | Meaning | Example |
|---|---|---|
| Root | The single top node — no parent | The trunk of the family tree |
| Parent | A node with at least one child below it | — |
| Child | A node directly below another node | — |
| Leaf | A node with no children (at the bottom) | A person with no children |
| Subtree | A node plus all its descendants | One branch of the family |
| Height | The number of edges on the longest path from root to a leaf | — |
| Level | The depth of a node — root is level 0 | — |
What is a binary tree?
A binary tree is the most important variety for GCSE: every node has at most two children, called the left child and the right child. A specific and very useful form is the binary search tree (BST):
- All values in the left subtree are less than the parent.
- All values in the right subtree are greater than the parent.
Building a BST from the sequence 8, 3, 10, 1, 6:
Insert 8 → root: 8
Insert 3 → 3 < 8, goes left of 8
Insert 10 → 10 > 8, goes right of 8
Insert 1 → 1 < 8 → left; 1 < 3 → left of 3
Insert 6 → 6 < 8 → left; 6 > 3 → right of 3
8
/ \
3 10
/ \
1 6
To search the BST for a value, you compare at each node and move left or right — exactly like binary search on a sorted list, but without the list.
How do you traverse a binary tree?
Traversal means visiting every node in a defined order. Three traversal orders appear in GCSE exams:
In-order (left → root → right)
Visits nodes in ascending order for a BST. Great for producing a sorted sequence.
Result on the tree above: 1, 3, 6, 8, 10
Pre-order (root → left → right)
Visits the root before its children. Useful for copying a tree.
Result: 8, 3, 1, 6, 10
Post-order (left → right → root)
Visits the root after its children. Used in expression evaluation and deleting trees.
Result: 1, 6, 3, 10, 8
A memory trick: the prefix tells you where the root sits in the sequence — pre = first, in = middle, post = last.
What are trees used for in real systems?
- File systems — folders and files form a tree where the root is the hard drive.
- HTML/XML parsing — a web page is stored internally as a tree of tags.
- Databases — B-trees index data for fast retrieval.
- Decision trees — each node is a question; leaves are outcomes. Used in machine learning and game AI.
- Expression trees — arithmetic expressions like
(3 + 5) × 2are stored as a tree to evaluate in the correct order.
How does a tree differ from a graph?
A tree is a restricted form of a graph. In a graph, any node can connect to any other; cycles (loops) are allowed. A tree imposes three additional rules:
- There is exactly one root.
- Every non-root node has exactly one parent.
- There are no cycles — you cannot follow edges and return to a node you have already visited.
If you remove any one of these rules, you have a general graph rather than a tree.
How do you answer tree questions in the GCSE exam?
Examiners typically ask you to:
- Build a BST by inserting values one at a time (show the tree at each step).
- Search a BST for a value and state how many comparisons are needed.
- Traverse a given tree and list the node visit order.
- Explain why a BST is more efficient for searching than a simple list.
Always draw clearly, label the root, and indicate left/right children when building or traversing.
Frequently asked questions
Can a tree have only one node?
Yes. A single node with no children is a valid tree — the root is also a leaf.
What is the difference between a tree and a linked list?
A linked list is effectively a tree where every node has at most one child (the next node). A binary tree allows up to two children per node, creating the branching structure.
Is a BST always faster than linear search?
A balanced BST gives O(log n) search time, like binary search. However, if values are inserted in sorted order, the BST degenerates into a linear chain and search becomes O(n) — as slow as a list. Balanced trees (such as AVL trees) fix this, but that is beyond GCSE scope.
Do all GCSE specifications include trees?
OCR and AQA both include trees and binary trees in their GCSE Computer Science specifications. Check your board's specification document to confirm which traversal methods are expected.
Want to practise building and traversing binary search trees with guided feedback? Visit aitutors.me and ask Professor Turing for a tree walkthrough.