B4.1.3 · Abstract data types (ADTs)
Binary trees & traversals
By the end you can
Trace binary tree hierarchies and recursive In-order, Pre-order, and Post-order tree traversals.
Unlike arrays and linked lists (which are linear), a is a non-linear, hierarchical data structure. It models hierarchical relationships such as file directories, compiler syntax trees, and game decision trees.
Tree terminology#
- : The top-most node of the tree with no parent. Every tree has exactly one root.
- Parent and Child: A node directly connected to another node below it is its parent; the lower node is its child. In a binary tree, each parent has at most two children (left child and right child).
- : A terminal node with no children (both child pointers are
null). - Height / Depth: The length of the longest path from the root to any leaf node.
Recursive tree traversals#
A is an algorithm that visits every node in a tree exactly once. Because trees are recursive data structures (each child is the root of its own subtree), traversals are written naturally using recursion:
- In-order (Left → Root → Right):Recursively traverse the left subtree, visit the root node, then traverse the right subtree. When applied to a Binary Search Tree, In-order traversal always produces elements in ascending numerical order!
- Pre-order (Root → Left → Right):Visit the root first, then the left subtree, then the right subtree. Used to duplicate or serialize a tree hierarchy.
- Post-order (Left → Right → Root):Traverse both subtrees first before visiting the root. Used when deleting nodes or evaluating arithmetic expression trees from leaves upward.
In-order (Left → Root → Right) — Step 1 of 7: Visited Node 20
Visits left subtree, then root, then right subtree. On a BST, In-order traversal ALWAYS produces ascending numerical sorted order!
Output Sequence So Far
Check yourself
Binary trees and traversals
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 9 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Define the following tree terms: root node, leaf node, subtree, and tree depth (height).
[4]Define: Give the precise meaning of the term.
2.Compare In-order, Pre-order, and Post-order recursive binary tree traversals in terms of node visit sequence.
[3]Compare: Similarities and differences, about both things, point by point.
3.Explain why trees are naturally suited to recursive algorithms and data definitions.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
In a nutshell
- A binary tree is a hierarchical, non-linear data structure where each node has at most two children (left and right).
- Key terminology: root (top node), leaves (terminal childless nodes), parent/child, and height (longest path length).
- In-order traversal (Left → Root → Right) visits nodes in ascending order on a binary search tree.
- Pre-order traversal (Root → Left → Right) is used for cloning/serializing, and Post-order (Left → Right → Root) for bottom-up node deletion.