Study Guide

Trees

CIE A-Level Computer ScienceΒ· Unit 10: Data types & structuresΒ· 40 min read

1. Core Tree Terminology & Propertiesβ˜…β˜…β˜†β˜†β˜†β± 10 min

πŸ“˜ Definition

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. 1

    Step 1: Calculate depth of E: path from root is A β†’ B β†’ E, which has 2 edges. Depth of E = 2.

  2. 2

    Step 2: Calculate height: the maximum depth of any leaf is 2 (E and F). Height of the tree = 2.

βœ“ Quick check

Test your understanding:

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

    • 0

    • 1

    • Undefined

    • Cannot be determined

    Reveal answer
    0 β€”

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

2. Binary Tree Depth-First Traversalβ˜…β˜…β˜…β˜†β˜†β± 15 min

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.

πŸ“˜ Definition

Depth-first traversal

A traversal that explores as far as possible along each branch before backtracking, almost always implemented recursively.

πŸ“ 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. 1

    Pre-order (Root β†’ Left β†’ Right): Visit A first, then traverse B's subtree, then C.

  2. 2

    B's pre-order: B β†’ D β†’ E. Final pre-order: A, B, D, E, C.

  3. 3

    In-order (Left β†’ Root β†’ Right): Traverse B's subtree first, then A, then C.

  4. 4

    B's in-order: D β†’ B β†’ E. Final in-order: D, B, E, A, C.

  5. 5

    Post-order (Left β†’ Right β†’ Root): Traverse B's subtree, then C, then A.

  6. 6

    B's post-order: D β†’ E β†’ B. Final post-order: D, E, B, C, A.

3. Binary Search Trees: Insertion & Searchβ˜…β˜…β˜…β˜†β˜†β± 15 min

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. 1

    Step 1: Insert 8 as the root node.

  2. 2

    Step 2: Insert 3: 3 < 8, add as left child of 8.

  3. 3

    Step 3: Insert 10: 10 > 8, add as right child of 8.

  4. 4

    Step 4: Insert 1: 1 < 8 β†’ move left to 3, 1 < 3 β†’ add as left child of 3.

  5. 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 for a balanced BST, but worst case is for an unbalanced tree.

βœ“ Quick check

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

    Reveal answer
    A straight line linked list β€”

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

4. Common Applications of Treesβ˜…β˜…β˜†β˜†β˜†β± 10 min

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 and give its pre-order traversal

  1. 1

    Step 1: The top-level operator is *, so * is the root. Right child is 2, left child is the + operator.

  2. 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.

5. Common Pitfalls

Wrong move:

Confusing node depth and tree height

Why:

Many students mix up which measurement counts from the root versus the deepest leaf

Correct move:

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 move:

Mixing up post-order traversal order

Why:

Students often place the root before the subtrees instead of after, by analogy to pre-order

Correct move:

Post-order = root last: always visit left subtree, then right subtree, then the current node.

Wrong move:

Inserting new BST nodes by rearranging existing nodes

Why:

Students think insertion requires rebalancing, but basic BST insertion always adds new nodes as leaves

Correct move:

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 move:

Claiming BST search is always time

Why:

Students forget that unbalanced BSTs lose their efficient search property

Correct move:

Only balanced BSTs have guaranteed search; unbalanced BSTs have worst-case search time.

Wrong move:

Stating a single root node has height 1

Why:

Some count nodes instead of edges when calculating height

Correct move:

CIE defines height as the number of edges, so a single node has height 0.

6. Quick Reference 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

average time

When this came up on past exams

AI-estimated based on syllabus patterns β€” cross-check with official past papers for accuracy. Use only as revision-focus signals.

  • 2022 Β· 1

    Tree traversal and BST construction

  • 2023 Β· 1

    Terminology and traversal question

  • 2024 Β· 1

    BST insertion and application

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.