OCR H446 · A Level Computer Science · ~13 min read
Notes
Video
Slides
Worksheet
Quiz
Trees
A tree is a hierarchical, connected, acyclic graph. It has a single root node at the top and every other node has exactly one parent. Trees are used to represent hierarchical data such as file systems, organisation charts, and expression trees.
Tree Terminology
Term
Definition
Root
The topmost node — has no parent
Node
Any element in the tree
Leaf (leaf node)
A node with no children
Parent
A node with at least one child
Child
A node directly below a parent
Sibling
Nodes that share the same parent
Edge
The link between a parent and child node
Height
Length of the longest path from root to a leaf
Depth / Level
Distance from the root (root = level 0)
Sub-tree
A node and all its descendants
Properties of Trees
A tree with n nodes has exactly n − 1 edges
There is exactly one path between any two nodes
Trees are acyclic (no cycles)
Trees are connected (every node reachable from root)
Binary Trees
A binary tree is a tree where each node has at most two children, known as the left child and right child.
Full binary tree: every node has 0 or 2 children (no node has only 1 child)
Complete binary tree: all levels fully filled except possibly the last, which is filled left to right
Perfect binary tree: all internal nodes have exactly 2 children; all leaves at same level. n = 2^(h+1) − 1 nodes
Balanced binary tree: height of left and right sub-trees of any node differ by at most 1
Binary Search Tree (BST)
A Binary Search Tree (BST) is a binary tree with the additional ordering property:
The left sub-tree of any node contains only values less than the node's value
The right sub-tree of any node contains only values greater than the node's value
Both sub-trees are themselves valid BSTs
This ordering makes searching, insertion, and deletion efficient.
BST Operations and Complexity
Operation
Average
Worst (unbalanced)
Search
O(log n)
O(n)
Insert
O(log n)
O(n)
Delete
O(log n)
O(n)
Worst case O(n) occurs when the BST degenerates to a linked list (e.g. inserting already-sorted data: 1, 2, 3, 4, 5 creates a chain leaning right).
BST Search Algorithm
-- Search BST for target value
function search(node, target):
if node is null: return "Not found"
if target == node.value: return "Found"
if target < node.value:
return search(node.left, target) -- go left
else:
return search(node.right, target) -- go right
BST Insert Algorithm
-- Insert value into BST
function insert(node, value):
if node is null: return new Node(value)
if value < node.value:
node.left = insert(node.left, value)
else if value > node.value:
node.right = insert(node.right, value)
return node -- (duplicate values ignored)
In-order traversal (left → node → right): 1, 3, 4, 6, 7, 8, 10, 14 — sorted ascending order! This is a key property of BSTs.
Tree Traversal Orders
Traversal
Order
Use
In-order
Left → Node → Right
Produces sorted output for BST
Pre-order
Node → Left → Right
Copying/serialising a tree
Post-order
Left → Right → Node
Deleting a tree; evaluating expressions
Real-world Uses of Trees
File system: directories as internal nodes, files as leaves
Organisation chart: manager → employees hierarchy
HTML/XML DOM: tags as nodes, nested content as children
Compilers: Abstract Syntax Tree (AST) from source code
Databases: B-Trees and B+-Trees for indexed lookups
Priority queues: Binary heaps implemented as complete binary trees
Exam tip: In-order traversal of a BST always gives values in ascending order. This is used to sort data. Pre-order: node first (useful for copying). Post-order: node last (useful for deletion). Know all three by heart.
Exam tip: BST worst case O(n) happens when data is inserted in sorted order — the tree becomes a linear chain (like a linked list). A balanced BST guarantees O(log n). Examiners often ask why worst case differs from average.
⚠ Common Mistakes
Confusing 'height' and 'depth' — height is the longest root-to-leaf path; depth of a node is its distance from root.
Saying BST search is always O(log n) — it's O(log n) average, O(n) worst case (degenerate/unbalanced tree).
Forgetting that a tree with n nodes has exactly n−1 edges. A connected, acyclic graph is a tree by definition.
✓ Notes completed!
▶
Video coming soon
Click to advance · Arrow keys also work
Click slide or press arrow keys to navigate
✍
Worksheet — 1.4.2d Trees and Binary Search Trees
8 questions · 20 marks · instantly marked
Q1Define the terms 'root', 'leaf', and 'sub-tree' in the context of a tree data structure.[3 marks]
✓ Mark scheme
Root: the topmost node in the tree — has no parent; all other nodes are descendants of the root [1]. Leaf: a node with no children — it is at the bottom/edge of the tree [1]. Sub-tree: a node along with all its descendants — forms a smaller tree structure within the main tree [1].
Q2How many edges does a tree with 12 nodes have? Justify your answer.[2 marks]
✓ Mark scheme
11 edges [1]. A tree with n nodes always has exactly n − 1 edges. This is because each node (except the root) has exactly one parent — so there are exactly n − 1 parent-child connections [1].
Q3State the ordering property of a Binary Search Tree (BST).[2 marks]
✓ Mark scheme
For any node in a BST: all values in the left sub-tree are less than the node's value [1]; all values in the right sub-tree are greater than the node's value [1]. Both sub-trees must also satisfy this property recursively.
Q4Draw the BST produced by inserting the following values in order: 15, 9, 20, 6, 12, 25. Show each node and the connections.[3 marks]
✓ Mark scheme
Root = 15 [1]. 9 goes left of 15 (9 < 15); 20 goes right of 15 (20 > 15); 6 goes left of 9 (6 < 9); 12 goes right of 9 (12 > 9 but < 15); 25 goes right of 20 (25 > 20) [1]. Correct final structure:
15
/ \
9 20
/ \ \
6 12 25 [1]
Q5For the BST in Q4 (root=15, nodes: 6,9,12,15,20,25), give the result of in-order, pre-order, and post-order traversal.[3 marks]
Q6Explain why the worst-case time complexity of BST search is O(n), and describe the scenario that causes this.[3 marks]
✓ Mark scheme
If data is inserted into a BST in already-sorted (or reverse-sorted) order, each new node becomes a child of the previous — the tree degenerates into a linear chain (like a linked list) [1]. For example, inserting 1, 2, 3, 4, 5 creates a right-leaning chain of 5 nodes [1]. To find the last item (5), you must traverse all n nodes, giving O(n) time complexity — there is no tree structure to exploit for O(log n) search [1].
Q7Trace through the BST search algorithm looking for the value 12 in the tree from Q4 (root=15, 9 left, 20 right, 6 and 12 children of 9, 25 child of 20). Show each comparison.[3 marks]
✓ Mark scheme
Start at root: compare 12 with 15 — 12 < 15, go left [1]. At node 9: compare 12 with 9 — 12 > 9, go right [1]. At node 12: compare 12 with 12 — match! Return Found. Total: 3 comparisons. O(log n) path taken through a balanced section [1].
Q8Give two real-world applications of tree data structures in computing systems.[4 marks]
✓ Mark scheme
Any two of [2 marks each]: File system — directories form a tree (root at top, sub-directories as child nodes, files as leaves); searching and navigating the file hierarchy uses tree traversal [2]. Database indexing — B-Trees/B+-Trees store sorted index entries; O(log n) record lookup without scanning entire table [2]. HTML/XML DOM — tags form a tree; CSS selectors and JavaScript DOM traversal use tree algorithms [2]. Compilers — Abstract Syntax Tree (AST) represents parsed source code; used in syntax checking, optimization, code generation [2].
Topic Quiz
1 of 15
You scored
out of 15
🎯
Mini Test — 1.4.2d Trees & BSTs
10 questions · 10 marks · 10 minutes
5 MCQ + 5 short answer
⏱10:00
10 marks
Section A — Multiple Choice
Q1A tree with 9 nodes has how many edges?
Q2In a BST, inserting values in already-sorted order (e.g. 1, 2, 3, 4, 5) results in:
Q3In-order traversal of a BST produces values in:
Q4Which traversal visits the node BEFORE its left and right sub-trees?
Q5A leaf node is a node that:
Section B — Short Answer
Q6State the BST ordering property in one sentence.
Mark schemeFor any node, all values in the left sub-tree are smaller than the node's value, and all values in the right sub-tree are greater. Both sub-trees must also satisfy this property. [1 mark]
Q7What traversal order would you use to sort the values in a BST? State the order (Left/Node/Right).
Mark schemeIn-order traversal: visit Left sub-tree, then Node, then Right sub-tree. This produces values in ascending sorted order for a BST. [1 mark]
Q8What is a 'balanced' binary tree?
Mark schemeA balanced binary tree is one where the heights of the left and right sub-trees of every node differ by at most 1. Balancing ensures O(log n) search/insert performance by preventing the tree from degenerating to a linear chain. [1 mark]
Q9What is the root node of a BST formed by inserting: 50, 30, 70, 20, 40?
Mark scheme50 — it is the first value inserted, becoming the root. The root of a BST is always the first value inserted. [1 mark]
Q10Give one real-world computing use of trees.
Mark schemeAny one of: file system (directories and files as tree nodes); HTML/XML Document Object Model (DOM); database B-tree indexing for fast record lookup; Abstract Syntax Tree (AST) in compilers; Huffman encoding tree for compression. [1 mark]