Define tree terminology: root, node, leaf, branch, subtree, height, depth
Describe a binary tree and its properties
Explain the structure and ordering property of a Binary Search Tree (BST)
Trace BST insertion and search operations
Tree Terminology
Trees — Key Terms
Structural Terms
Root: single top-most node — no parent Node: any element in the tree Leaf (terminal): node with no children Branch (edge): connection between nodes Subtree: a node and all its descendants
Measurement Terms
Height: number of edges on the longest path from root to a leaf Depth: number of edges from root to a specific node Degree: number of children a node has
A tree is a connected, acyclic (no cycles), directed graph with one root node. Each node (except root) has exactly one parent. Trees are hierarchical — unlike graphs, there is always a clear top-down structure.
Binary Trees
Binary Trees
A binary tree is a tree in which every node has at most two children — referred to as the left child and the right child. Each node stores: data, a pointer to the left child, and a pointer to the right child (null if no child).
Types of Binary Tree
Full: every node has 0 or 2 children Complete: all levels filled except possibly the last (filled left-to-right) Balanced: height is O(log n) — ensures efficient operations
A BST is a binary tree with the following ordering property: for any node N, all values in the left subtree are less than N, and all values in the right subtree are greater than N. This enables efficient O(log n) search, insert and delete on a balanced BST.
BST Insert: 50, 30, 70, 20, 40
50
/ \
30 70
/ \
20 40
Search for 40
Start at root (50): 40 < 50 → go left At 30: 40 > 30 → go right At 40: found! ✓
3 comparisons — O(log n) for balanced BST
BST Operations
BST Insert Algorithm
procedure insert(node, value):
if node = null then create node with value
else if value < node.data then
node.left = insert(node.left, value)
else if value > node.data then
node.right = insert(node.right, value)
return node
Worst case: if values are inserted in sorted order (e.g. 10, 20, 30, 40), the BST degrades to a linked list with O(n) search. This is why self-balancing trees (AVL, Red-Black) exist.
Exam Practice
OCR H446 Style · 4 marks
The values 45, 20, 60, 10, 35, 55, 70 are inserted into an initially empty BST in this order. Draw the resulting BST and state the number of comparisons needed to search for the value 35.
[4 marks]
2
BST structure: Root=45. Left subtree: 20 (left:10, right:35). Right subtree: 60 (left:55, right:70). (Award 2 marks for correct structure with proper left/right placement at each level.)
1
Search for 35: compare with 45 (35<45 → left), compare with 20 (35>20 → right), compare with 35 (found) = 3 comparisons.
1
This demonstrates O(log n) search efficiency — with 7 nodes the maximum depth is 3, requiring at most 3 comparisons on the balanced tree.
Common Mistakes
Don't Lose Marks
!
Placing equal values incorrectly in a BST — the standard OCR BST rule is strict: left < node < right. Equal values are typically not inserted (or placed to the right — check what the question specifies). Do not arbitrarily place duplicates.
!
Confusing tree height and depth — height is measured from a node downward to the furthest leaf; depth is measured from the root downward to a specific node. The height of the tree = height of the root = maximum depth of any leaf.
!
Saying BST search is always O(log n) — O(log n) only applies to a balanced BST. An unbalanced BST (e.g. sorted insertions) degrades to O(n). OCR may ask about worst-case complexity — always qualify with "balanced".