Community resourceWorksheet
OCR H446 1.4.2 Trees and hierarchical structures
Part 9 of 14 · H446 1.4.2 · Data structures
A festival programme of categories and activities gives H446 1.4.2 tree vocabulary something concrete to describe. This worksheet holds students to exact terms for the parts of a tree, then makes the point that removing an internal node needs a stated policy, because the structure alone does not decide one.
Students will:
- use root, parent, child, sibling, leaf, subtree and depth accurately under a stated depth convention
- distinguish binary from multi-branch trees and read child-pointer values including absent children
- choose and state a removal policy for an internal node rather than assuming one
- contrast breadth-first and depth-first traversal by the state each one keeps
- design a media-library hierarchy and justify the tree type, one traversal purpose and one removal
Inside: 7 explanation cells, 3 multiple-choice questions, 1 fill-in-the-blanks cell and 4 written answers. 30 marks, about 50 to 60 minutes.
Series: H446 1.4.2 · Data structures, part 9 of 14.
Shared by Coding PathwayVerified teacher
- 15 cells
- About 60 minutes
- CC BY-SA 4.0
- Shared 31 Aug 2026
- Updated 1 Oct 2026
Preview
The whole resource, exactly as a class sees it. Answers and marking are held back.
Trees and hierarchical structures
A tree is a connected graph with no cycles. In a rooted tree, every node except the root has one parent. This makes a tree suitable for a hierarchy such as folders, categories or an organisation chart.
By the end, you will be able to
- use root, parent, child, sibling, leaf, subtree and depth;
- distinguish binary and multi-branch trees;
- explain depth-first and breadth-first traversal state;
- add and remove nodes using a clearly stated policy.
Read the hierarchy
Festival is the root. Stages and Workshops are siblings. Code is a leaf. The Workshops subtree contains Workshops and all descendants. A binary tree allows each node at most two children; this multi-branch tree allows more.
Worked operation and traversal policy
Adding a workshop attaches a new child to Workshops. Removing a leaf is direct. Removing an internal node needs a stated policy: remove its whole subtree, promote children, or reject until empty. The structure alone does not decide policy.
In an array-backed binary tree, a child field stores another node index; −1 means no child at that particular link. A node is a leaf only when it has no children. Depth-first traversal follows a branch and uses recursive calls or a stack to remember where to backtrack. Breadth-first traversal uses a queue to visit one level before the next.
What does binary tree mean?
- AEvery node always has two children
- BThe tree stores only 0 and 1
- CEvery node has at most two children
- DThe tree has two levels
A binary-tree node has left = −1 and right = 7. Which conclusion is valid?
- AIt is a leaf because one pointer is −1
- BNode 7 must be its parent
- CThe whole tree is empty
- DIt has no left child but does have a right child, so it is not a leaf
Which state mechanism matches the traversal?
- ADepth-first uses recursion or a stack for backtracking; breadth-first uses a queue
- BDepth-first must use a queue; breadth-first must use no state
- CBoth traversals always visit nodes alphabetically
- DBreadth-first follows one branch to a leaf before remembering siblings
Guided vocabulary
For each node, state parent, children and whether leaf. Then give depth with root depth 0. Naming the convention prevents off-by-one disagreement.
Using the diagram, state the root, the parent of Art, the siblings of Code, and all leaves.
Use the displayed hierarchy.
Students type their answer here.
Starting at Festival, give the first five nodes visited by (a) breadth-first traversal and (b) depth-first pre-order traversal, reading siblings from left to right. Explain why breadth-first uses a queue and depth-first uses a stack or recursive call stack.
Write each visit order, then connect the state structure to what must be remembered next.
Students type their answer here.
Independent transfer
Design a tree for a school media library with top categories, subcategories and items. Include both a binary or multi-branch choice and a removal policy.
Give at least eight labelled nodes and their relationships. Justify the tree type, describe one useful traversal, add one item, and explain how an internal category would be removed.
For the removal, state what happens to every descendant.
Students type their answer here.
Explain why a tree may model the festival hierarchy more clearly than a flat list.
Use relationships and traversal.
Students type their answer here.
Closed-book checkpoint
Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.
Review your work
Check that your tree vocabulary describes relationships precisely. Only apply the ‘at most two children’ rule when the tree is explicitly binary.