Understand trees as a connected, undirected graph with no cycles, the terms root, child, parent, leaf and subtree, and the structure and use of a binary search tree.

What this dot point is asking

AQA wants you to define a tree as a connected, undirected graph with no cycles, use the terminology (root, child, parent, leaf, subtree), and explain the structure and use of a binary search tree.

Trees and terminology

Trees model hierarchical data such as file systems (folders containing folders and files), family trees, organisation charts, the document object model of a web page, and the structure of a parsed expression. Two further terms are useful: the height of a tree is the number of levels from the root to the deepest leaf, and a node's depth is its distance from the root. Height is what determines how long operations on a tree take.

Binary trees

A binary tree is a tree in which each node has at most two children, conventionally called the left child and the right child. Each node typically stores a data value plus pointers (references) to its left and right children, with a null pointer where a child is absent. This pointer-based structure is dynamic: nodes are created and linked at run time, so the tree grows and shrinks as needed, which is one reason trees are studied alongside other dynamic structures.

Binary search trees

The BST therefore combines two useful properties: fast search (like binary search on a sorted array) and easy insertion (no need to shift elements as you would in an array). The price is that the good performance depends on the tree staying reasonably balanced. If items are inserted in already-sorted order the tree becomes unbalanced, effectively a linked list of height $n$, and operations degrade to $O(n)$. Self-balancing variants address this in practice, but the core specification focuses on the ordered structure and its traversal.

It is worth comparing a BST with a hash table, since both store data for fast retrieval. A hash table gives average $O(1)$ look-up by key but keeps the data unordered, so it cannot easily produce the items in sorted order or answer range queries (all values between two bounds). A binary search tree gives $O(\log n)$ look-up when balanced, which is slightly slower, but its in-order traversal yields sorted output for free and range queries are straightforward. Choosing between them is a genuine design decision: a hash table when you only ever look up exact keys, a search tree when order matters.

Deletion from a BST is the operation students find hardest because there are three cases: removing a leaf simply detaches it; removing a node with one child links the parent directly to that child; removing a node with two children requires replacing it with its in-order successor (the smallest value in its right subtree) so the ordering rule is preserved. Understanding why the successor is chosen, namely that it is the next value in sorted order and so keeps everything to its left smaller and right larger, shows a real grasp of the structure rather than rote recall.