Binary Trees

This lesson covers binary trees — a hierarchical data structure central to the OCR A-Level Computer Science (H446) specification. Binary trees are used in searching, sorting, expression parsing, and many other computing applications.

---

What is a Tree?

A tree is a non-linear, hierarchical data structure consisting of nodes connected by edges. Unlike linear structures (arrays, linked lists), trees branch out, allowing for efficient organisation of data.

Key Terminology

Term	Definition
Root	The topmost node in the tree (has no parent).
Node	An element in the tree, containing data.
Edge	A connection between a parent node and a child node.
Parent	A node that has one or more child nodes.
Child	A node that has a parent node.
Leaf	A node with no children (also called a terminal node).
Subtree	A tree formed by any node and all its descendants.
Depth	The number of edges from the root to a given node.
Height	The number of edges on the longest path from the root to a leaf.
Level	Nodes at the same depth (root is level 0).

---

What is a Binary Tree?

A binary tree is a tree where each node has at most two children, referred to as the left child and right child.

Structure

        [Root]
       /      \
    [Left]   [Right]
    /    \       \
 [L-L]  [L-R]  [R-R]

Node Structure

record TreeNode
    data: integer
    left: TreeNode    // pointer to left child (or null)
    right: TreeNode   // pointer to right child (or null)
end record

Python Implementation

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

---

Binary Search Trees (BSTs)

A Binary Search Tree is a binary tree with an additional ordering property:

• All values in the left subtree are less than the node's value.
• All values in the right subtree are greater than the node's value.

This property applies recursively to every node in the tree.

Example

Insert values: 8, 3, 10, 1, 6, 14, 4, 7, 13

           8
         /   \
        3     10
       / \      \
      1   6     14
         / \    /
        4   7  13

Building a BST — Step by Step

Step	Value	Action
1	8	Becomes the root
2	3	3 < 8, go left. Left is empty, insert here.
3	10	10 > 8, go right. Right is empty, insert here.
4	1	1 < 8, go left (3). 1 < 3, go left. Empty, insert here.
5	6	6 < 8, go left (3). 6 > 3, go right. Empty, insert here.
6	14	14 > 8, go right (10). 14 > 10, go right. Empty, insert here.
7	4	4 < 8 (left to 3). 4 > 3 (right to 6). 4 < 6 (left). Empty, insert.
8	7	7 < 8 (left to 3). 7 > 3 (right to 6). 7 > 6 (right). Empty, insert.
9	13	13 > 8 (right to 10). 13 > 10 (right to 14). 13 < 14 (left). Insert.