Community resourceWorksheet

OCR H446 2.3.1 Tree operations

Part 11 of 16 · H446 2.3.1 · Algorithms

Tree questions in H446 2.3.1 depend on the policy in force: a binary tree limits children to two, while a binary search tree adds the ordering rule that makes searching possible. This worksheet separates those two ideas, then works insertion, search and the awkward two-child deletion under an explicit rule.

Students will:

  • distinguish the binary tree definition from the additional ordering rule of a BST
  • follow and record a comparison path down to the null child where a value belongs
  • delete leaf, one-child and two-child nodes using a consistently chosen replacement
  • implement an iterative BST search over nodes held as dictionaries
  • explain how insertion order can flatten a tree into a chain and what that costs

Inside: 5 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers and 1 Python task. 25 marks, about 25 to 40 minutes.

Series: H446 2.3.1 · Algorithms, part 11 of 16.

Shared by Coding PathwayVerified teacher

  • 10 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Tree operations

Tree algorithms depend on the tree's policy. A binary tree has at most two children; it does not require every node to have two. A BST also applies smaller-left/larger-right ordering.

By the end, you will be able to

  • create/search/add/remove nodes under a stated policy;
  • distinguish binary tree from BST;
  • trace recursive and iterative search;
  • relate height/shape to work.

Reactivate: root, parent, child, leaf, subtree and height.

Worked BST operations

Search 55 in root 50, right 70, left-of-70 60: compare 50 (right), 70 (left), 60 (left), then reach null, so the value is not found. Insert 55 at that null child.

Delete: leaf detaches; one-child node promotes its child; two-child node uses a consistently chosen in-order successor/predecessor then removes the moved value.

Multiple choice1 mark

Which statement defines a binary tree?

  • AEvery node has exactly two children
  • BValues are always sorted
  • CEvery node has at most two children
  • DIt is always balanced
Written answer8 marks

Starting with BST values 50,30,70,20,40,60,80, insert 55 and delete 30 using the in-order successor. Show comparison paths and final links.

State the two-child deletion policy.

Students type their answer here.

Independent transfer: iterative BST search

Nodes are dictionaries containing value, left and right; missing child is None.

Coding task6 marks
def bst_search(node, target):
    pass
Written answer5 marks

Compare search work in a balanced BST and a chain-shaped BST. Explain how insertion order can create the chain.

Use height and input order.

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.

Fill in the blanks5 marks
A completion 1 tree permits at most two children per node. A completion 2 additionally orders smaller and larger values. Deleting a completion 3 detaches it; deleting a two-child node may use its in-order completion 4. Search work depends on tree completion 5.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.