4.2.5 Trees & Binary Trees — AQA 7517

What is a Tree?

A tree is a connected, acyclic (no cycles) directed graph with a single root node. All other nodes descend from the root via parent-child relationships.

Tree Terminology

Term	Definition
Root	The top node — has no parent
Node	Any element in the tree
Edge	A directed connection from parent to child
Leaf (terminal node)	A node with no children
Parent	A node directly above another node
Child	A node directly below a parent
Subtree	Any node and all of its descendants
Height/depth	Length of the longest path from root to leaf

Binary Tree

A binary tree is a tree where each node has at most two children — a left child and a right child.

Binary Search Tree (BST)

A binary search tree is an ordered binary tree where:

Values in the left subtree are less than the node's value
Values in the right subtree are greater than the node's value
No duplicate values

// Build BST from: 50, 30, 70, 20, 40, 60, 80
         50
        /  \
       30   70
      / \  / \
     20 40 60 80
// Search for 40: 50 → left → 30 → right → 40 ✓ (O(log n) average)

BST Operations

Operation	Average	Worst (unbalanced)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

The worst case occurs when data is inserted in sorted order, creating a linear chain (degenerate tree).

Tree Traversals (see also 4.3.2)

Pre-order: Root → Left → Right
In-order: Left → Root → Right (gives sorted order for BST)
Post-order: Left → Right → Root

Applications of Trees

Binary search trees — efficient search, insert, delete
File system hierarchies — directories and subdirectories
Parse trees / syntax trees — compilers represent code structure
Decision trees — AI classification
Huffman coding trees — data compression

Exam tip: Know all tree terminology. Be able to build a BST from given data, state the order of traversal (pre/in/post-order), and know that in-order traversal of a BST gives sorted ascending order. Know average vs worst-case complexity.

▶

Click through the slides at your own pace. Use arrow keys or click to advance.

Click slide or press arrow keys to navigate

Worksheet — 4.2.5 Trees & Binary Trees

8 questions · instantly marked · AQA 7517 standard

Q1Define 'root', 'leaf', and 'subtree' in the context of a tree data structure.[3]

✅ Mark scheme

Mark scheme

Root — the top node that has no parent [1]; Leaf (terminal node) — a node with no children [1]; Subtree — any node and all of its descendants [1].

Q2What distinguishes a binary tree from a general tree?[1]

✅ Mark scheme

Mark scheme

Each node in a binary tree can have at most two children (left and right) [1].

Q3Build a BST by inserting the values 40, 20, 60, 10, 30, 50, 70 in order. Describe the resulting structure.[4]

✅ Mark scheme

Mark scheme

Root = 40 [1]; 20 is left child of 40, 60 is right child of 40 [1]; 10 is left child of 20, 30 is right child of 20 [1]; 50 is left child of 60, 70 is right child of 60 [1].

Q4State the two ordering rules of a Binary Search Tree.[2]

✅ Mark scheme

Mark scheme

Values in the left subtree are less than the node value [1]; values in the right subtree are greater than the node value [1].

Q5State the in-order traversal of the BST in Q3 and explain what is significant about the result.[2]

✅ Mark scheme

Mark scheme

In-order: 10, 20, 30, 40, 50, 60, 70 [1]; in-order traversal of a BST always produces the values in sorted ascending order [1].

Q6What is the average-case time complexity of searching a BST? When does the worst case arise and what is it?[3]

✅ Mark scheme

Mark scheme

Average: O(log n) [1]; worst case arises when data is inserted in sorted order, creating a linear/degenerate chain [1]; worst-case complexity is O(n) [1].

Q7State the order of traversal for pre-order and post-order. Give the pre-order for the BST in Q3.[3]

✅ Mark scheme

Mark scheme

Pre-order: Root → Left → Right [1]; Post-order: Left → Right → Root [1]; Pre-order of Q3 BST: 40, 20, 10, 30, 60, 50, 70 [1].

Q8Give two real-world applications of trees in computing.[2]

✅ Mark scheme

Mark scheme

Any two: file system hierarchy [1]; parse/syntax trees in compilers [1]; Huffman coding for compression [1]; decision trees in AI [1]; HTML/DOM representation [1].

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 12

Click to reveal definition

🎉

All cards reviewed!

Term	Definition

🔒

Pro Content

Subscribe to unlock all AQA 7517 A-Level lessons.

£7.99/month

Upgrade to Pro

What is a Tree?

Tree Terminology

Binary Tree

Binary Search Tree (BST)

BST Operations

Tree Traversals (see also 4.3.2)

Applications of Trees

Worksheet — 4.2.5 Trees & Binary Trees

Mini Test — Trees