Trees (including binary trees) — AQA A-Level Computer Science
A tree is a non-linear, connected, acyclic data structure composed of nodes connected by edges, featuring a designated root node. In AQA A-Level Computer Science, binary trees restrict each node to at most two children, enabling efficient O(log n) searching, insertion, and traversal routines.
Trees (including binary trees) explained
A tree is a graph with three linked properties that you must know together: it is connected, meaning there is a path between every pair of vertices; it is undirected, meaning each edge joins two vertices with no direction of travel; and it has no cycles, meaning no path starts and ends at the same vertex without repeating an edge. Because the graph is connected and acyclic, there is exactly one simple path between any two vertices. A useful check is to count edges: a tree with n vertices always has exactly n − 1 edges. For example, a graph with 5 vertices and 4 edges that links every vertex is a tree, but adding a fifth edge between two existing vertices creates a cycle and so the graph is no longer a tree. In a question, test each property separately: confirm connectivity, confirm there are no directed edges, and search for any closed loop.
Your focus
- Know that a tree is a connected, undirected graph with no cycles.
Which command word is this?
Provide a concise, factual answer without detailed explanation, such as naming a traversal type or listing the output sequence.
Trees (including binary trees) exam tips
Topic Overview
Trees are fundamental non-linear dynamic data structures used across computer science to represent hierarchical relationships. They are widely applied in operating system directory structures, expression evaluation, syntax analysis in compilers, and search indices.
Within the AQA specification, students must master tree nomenclature, binary tree representations in arrays or records, recursive tree traversals (pre-order, in-order, and post-order), and the operational algorithms for searching, adding, and deleting nodes.
Key Concepts
- →A tree is an undirected, connected graph with no cycles; a rooted tree designates a top node from which all paths originate.
- →A binary tree is a rooted tree where every node has at most two child nodes, commonly referred to as the left child and right child.
- →Binary Search Trees (BSTs) enforce an ordering property: all values in the left subtree are smaller than the node, and all values in the right subtree are greater.
- →Traversals visit every node systematically: Pre-order (Root, Left, Right), In-order (Left, Root, Right), and Post-order (Left, Right, Root).
- →Trees can be stored in memory using arrays of records containing data fields alongside left-child and right-child pointer indices.
Marking Points
- Defines a tree as a graph that is connected, undirected and contains no cycles.
- Identifies a disconnected graph as not a tree, even if it has no cycles.
- Identifies a graph containing a closed loop as not a tree, even if it is connected.
- Uses the edge count of n − 1 as a valid check for a tree on n vertices.
- Recognises that a directed graph is not an undirected tree.
Examiner Tips
- 💡Check the three properties in turn: connected, undirected, no cycles.
- 💡Use the edge count n − 1 as a quick test, then confirm connectivity and acyclicity.
- 💡Eliminate options that include a cycle or a disconnected component before selecting the answer.
- 💡Always check whether the question specifies numerical or alphabetical order before constructing a binary search tree.
- 💡When drawing arrays to represent binary trees, ensure unused child pointers are clearly set to a null indicator, such as -1 or null.
- 💡Memorise the standard recursive traversal algorithms in pseudocode; questions frequently require filling in missing recursive base cases or function calls.
Common Mistakes
- Treats any graph with no cycles as a tree; the graph must also be connected. Check connectivity before concluding.
- Counts a graph with a closed loop as a tree because it looks branched; a cycle of any length rules out a tree.
- Assumes a tree must have a designated root; this belongs to a rooted tree, not to the definition of a tree in general.
- Assuming all trees are binary trees: General trees can have any arbitrary number of child nodes per parent; binary trees are restricted to a maximum of two.
- Believing BST searching is always O(log n): If inserted data is already sorted, the tree becomes degenerate (unbalanced), reducing efficiency to O(n).
- Confusing pre-order with breadth-first search: Pre-order is a depth-first traversal strategy that explores down to the leaves before backtracking, not level-by-level.
Revision Plan
- 1Day 1-2: Review tree terminology (root, leaf, height, subtree) and graph theory definitions.
- 2Day 3-4: Practice constructing binary search trees by hand from random, ordered, and reverse-ordered lists.
- 3Day 5-6: Master tree traversals (pre-order, in-order, post-order) using the outline tracing technique and write recursive pseudocode for each.
- 4Day 7-8: Practice array-of-records table representations with left/right pointers and complete past AQA exam questions.
Exam Question Types
- 📋Diagram construction: Inserting an ordered sequence of data into a binary search tree and identifying leaf nodes.
- 📋Traversal traces: Writing the exact output order for pre-order, in-order, or post-order traversal on a provided tree diagram.
- 📋Implementation and memory: Filling in or tracing an array of records with LeftChild, Data, and RightChild columns.
- 📋Algorithm evaluation: Comparing time complexities of balanced vs unbalanced trees, or writing recursive algorithms for searching/adding nodes.
Command Word Expectations (AQA)
Provide a concise, factual answer without detailed explanation, such as naming a traversal type or listing the output sequence.
Give reasons and show how or why a particular structure or algorithm behaves in a certain way, using accurate technical terms.
Follow the step-by-step execution of an algorithm or traversal, recording intermediate variables or values visited in exact sequence.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: The following items are inserted into an empty Binary Search Tree (BST) in order: 'Mango', 'Apple', 'Peach', 'Banana', 'Orange'. Draw the resulting BST and state the output sequence of a post-order traversal.
- 1.Step 1: 'Mango' becomes the root node.
- 2.Step 2: Compare 'Apple' to 'Mango'. 'Apple' precedes 'Mango' alphabetically, so it becomes the left child of 'Mango'.
- 3.Step 3: Compare 'Peach' to 'Mango'. 'Peach' succeeds 'Mango', so it becomes the right child of 'Mango'.
- 4.Step 4: Compare 'Banana' to 'Mango' (left), then to 'Apple' (succeeds 'Apple'), so 'Banana' becomes the right child of 'Apple'.
- 5.Step 5: Compare 'Orange' to 'Mango' (right), then to 'Peach' (precedes 'Peach'), so 'Orange' becomes the left child of 'Peach'.
- 6.Step 6: Trace post-order traversal using the order Left, Right, Root. The left subtree of 'Mango' contains 'Apple' and 'Banana', yielding 'Banana', 'Apple'. The right subtree contains 'Peach' and 'Orange', yielding 'Orange', 'Peach'. Finally, visit the root 'Mango'.
Question: Explain the time complexity of searching for an item in a balanced binary search tree compared to a degenerate binary search tree with n nodes.
- 1.Step 1: Define the structure of a balanced BST. In a balanced BST, each node splits the remaining search space roughly in half at each step.
- 2.Step 2: State the time complexity for a balanced BST. Because the height of a balanced tree is proportional to log2(n), searching has a time complexity of O(log n).
- 3.Step 3: Define a degenerate BST. A degenerate tree occurs when items are added in sorted or reverse-sorted order, causing each node to have only one child.
- 4.Step 4: State the time complexity for a degenerate BST. The structure becomes effectively a linear linked list of height n, requiring every node to potentially be checked, giving O(n) worst-case time complexity.