# Trees

> CIE A-Level Computer Science · 9618
> Source: https://www.owlsprep.com/study/cie-9618-u10-trees/

Trees are hierarchical non-linear data structures used to organise data efficiently. This module covers core terminology, traversal methods, binary search trees, and common practical applications of trees for CIE A-Level.

**Prerequisites:** [Recursion fundamentals](https://www.owlsprep.com/study/cie-9618-u09-recursion/); [Linked list basics](https://www.owlsprep.com/study/cie-9618-u09-linked-lists/)

## Learning objectives

- Define core tree terminology and properties
- Perform all three common depth-first binary tree traversals
- Construct binary search trees and perform insertion/search
- Identify common practical applications of trees

## Core Tree Terminology & Properties

**Tree** — A hierarchical non-linear data structure consisting of nodes connected by edges, with one root node and no cycles. Every node except the root has exactly one parent node.

*Example:* A computer file system's directory structure

Key terms describe the structure and measurements of a tree:

- Root: topmost node with no parent
- Leaf: node with no children
- Depth of a node: number of edges from the root to the node
- Height of a tree: maximum depth of any leaf node
- Binary tree: each node has at most 2 children (left and right)

**Worked example:** Given a tree with root A, children B, C, D. B has children E and F. What is the depth of E, and the height of the tree?

1. Step 1: Calculate depth of E: path from root is A → B → E, which has 2 edges. Depth of E = 2.
2. Step 2: Calculate height: the maximum depth of any leaf is 2 (E and F). Height of the tree = 2.

**Check your understanding**

Test your understanding:

1. What is the height of a single root node with no children?

   - 0
   - 1
   - Undefined
   - Cannot be determined

   *Why:* The height is the maximum depth of any leaf, and the root itself has depth 0, so height is 0 per CIE definitions.

## Binary Tree Depth-First Traversal

Traversal is the process of visiting every node in a tree exactly once in a defined order. For binary trees, three common depth-first traversal methods are named for the order the root node is visited relative to its subtrees.

**Depth-first traversal** — A traversal that explores as far as possible along each branch before backtracking, almost always implemented recursively.

> **Order Mnemonic**
>
> Root position gives the order: Pre = Root first, In = Root between, Post = Root last. This matches prefix/infix/postfix notation for expression trees!

**Worked example:** List the nodes of the following binary tree in pre-order, in-order, and post-order: Root = A, left child B, right child C. B has left D, right E. C has no children.

1. Pre-order (Root → Left → Right): Visit A first, then traverse B's subtree, then C.
2. B's pre-order: B → D → E. Final pre-order: A, B, D, E, C.
3. In-order (Left → Root → Right): Traverse B's subtree first, then A, then C.
4. B's in-order: D → B → E. Final in-order: D, B, E, A, C.
5. Post-order (Left → Right → Root): Traverse B's subtree, then C, then A.
6. B's post-order: D → E → B. Final post-order: D, E, B, C, A.

## Binary Search Trees: Insertion & Search

A Binary Search Tree (BST) is a binary tree with a special ordering property that enables efficient search and insertion of values. The BST property states that for any node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater than the node's value.

**Worked example:** Construct a BST by inserting values in this order: 8, 3, 10, 1, 6

1. Step 1: Insert 8 as the root node.
2. Step 2: Insert 3: 3 < 8, add as left child of 8.
3. Step 3: Insert 10: 10 > 8, add as right child of 8.
4. Step 4: Insert 1: 1 < 8 → move left to 3, 1 < 3 → add as left child of 3.
5. Step 5: Insert 6: 6 < 8 → move left to 3, 6 > 3 → add as right child of 3.

Search in a BST works by recursively comparing the target value to the current node, moving left if the target is smaller, right if larger. Average time complexity for search/insert is $O(\log n)$ for a balanced BST, but worst case is $O(n)$ for an unbalanced tree.

**Check your understanding**

Check your knowledge:

1. If you insert sorted values [1, 2, 3, 4, 5] into a BST, what will the resulting structure look like?

   - A straight line linked list
   - A balanced tree
   - A full binary tree
   - A complete binary tree

   *Why:* Each new value is larger than the current node, so it is always added as the right child, resulting in an unbalanced linear structure.

## Common Applications of Trees

Trees are widely used in computing because their hierarchical structure supports efficient organisation and search. Key applications you need to know for CIE are:

- Expression trees: store arithmetic expressions, with operators as internal nodes and operands as leaves
- File system directories: represent the hierarchical folder structure
- Heaps: implement priority queues and heap sort
- Huffman coding trees: used for lossless data compression
- Abstract syntax trees: used by compilers to parse code

**Worked example:** Draw the expression tree for infix $(3 + 4) * 2$ and give its pre-order traversal

1. Step 1: The top-level operator is *, so * is the root. Right child is 2, left child is the + operator.
2. Step 2: + has left child 3 and right child 4. Pre-order traversal visits root first: * + 3 4 2, which is the prefix notation of the expression.

## Common pitfalls

- **Wrong:** Confusing node depth and tree height
  - Why it fails: Many students mix up which measurement counts from the root versus the deepest leaf
  - Correct: Depth of a node counts edges from the root to the node; height of the tree counts edges from the root to the deepest leaf.
- **Wrong:** Mixing up post-order traversal order
  - Why it fails: Students often place the root before the subtrees instead of after, by analogy to pre-order
  - Correct: Post-order = root last: always visit left subtree, then right subtree, then the current node.
- **Wrong:** Inserting new BST nodes by rearranging existing nodes
  - Why it fails: Students think insertion requires rebalancing, but basic BST insertion always adds new nodes as leaves
  - Correct: Start at the root, move left/right following BST rules until you find an empty spot, then add the new node as a leaf.
- **Wrong:** Claiming BST search is always $O(\log n)$ time
  - Why it fails: Students forget that unbalanced BSTs lose their efficient search property
  - Correct: Only balanced BSTs have guaranteed $O(\log n)$ search; unbalanced BSTs have worst-case $O(n)$ search time.
- **Wrong:** Stating a single root node has height 1
  - Why it fails: Some count nodes instead of edges when calculating height
  - Correct: CIE defines height as the number of edges, so a single node has height 0.

## Cheatsheet

| Term | Key Fact |
| --- | --- |
| Root Node | Top node, no parent |
| Leaf Node | Node with no children |
| Node Depth | Number of edges from root to node |
| Tree Height | Maximum depth of any leaf |
| Pre-order | Root → Left → Right |
| In-order | Left → Root → Right |
| Post-order | Left → Right → Root |
| BST Property | All left values < node < all right values |
| Balanced BST Search | $O(\log n)$ average time |

## What's next

Trees are a foundational non-linear data structure that underpin many advanced algorithms and data structures across the CIE 9618 syllabus. A solid understanding of tree properties, traversal, and binary search trees is critical for answering both theory and algorithm design questions on Paper 1. Trees also introduce core hierarchical thinking that translates directly to the next major non-linear data structure, graphs, and supports topics like expression evaluation and searching in later units.

- [Graphs](https://www.owlsprep.com/study/cie-9618-u10-graphs/)
- [Hash tables](https://www.owlsprep.com/study/cie-9618-u10-hash-tables/)
- [Programming](https://www.owlsprep.com/study/cie-9618-u11-overview/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u10-trees/