Community resourceWorksheet

OCR H446 1.4.2 Binary search trees: operations

Part 10 of 14 · H446 1.4.2 · Data structures

The binary search tree in H446 1.4.2 is where ordering becomes an operation: each comparison discards a whole subtree. This worksheet works through search, insertion, the three deletion cases and the depth-first traversal orders, and closes on why the shape of the tree, not just its contents, decides how well search performs.

Students will:

  • apply the ordering invariant across a whole subtree rather than to one parent comparison
  • search for and insert values by repeated comparison, giving the comparison path taken
  • handle removal of leaf, one-child and two-child nodes consistently
  • give pre-order, in-order and post-order traversals and say which produces sorted output
  • explain how already sorted input can leave a tree behaving much like a linked list

Inside: 10 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 3 written answers and 2 Python tasks. 33 marks, about 50 to 60 minutes.

Series: H446 1.4.2 · Data structures, part 10 of 14.

Shared by Coding PathwayVerified teacher

  • 17 cells
  • About 60 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.

Binary search trees: operations

A score index uses ordering to choose left or right at each node. The invariant enables directed search but shape matters.

By the end, you will be able to

  • apply the BST ordering invariant;
  • search and add by repeated comparison;
  • remove leaf, one-child and two-child nodes;
  • explain how shape affects operations.

Reactivate: a binary tree allows at most two children.

Ordering invariant

Binary search tree ordering invariant50307020406080smaller subtreelarger subtree

For this convention, every value in a node’s left subtree is smaller and every value in its right subtree is larger. Duplicate policy must be stated separately.

Worked search and insertion

Search 60: compare 50 (go right), compare 70 (go left), find 60. Insert 65: 50→right, 70→left, 60→right, attach as a leaf.

Check the entire subtree invariant, not only the parent comparison.

Multiple choice1 mark

Which statement is true of the displayed BST?

  • AAll left descendants of 50 are smaller than 50
  • BEvery node has two children
  • CValues are stored in insertion order across each level
  • DSearch must visit every node

Worked deletion cases

Leaf: detach it. One child: connect the parent directly to the child. Two children: replace with a consistent in-order predecessor or successor, then remove that moved value from its old position.

Deleting 70 could replace it with successor 80 or predecessor 60 under a stated method. Show all affected links.

Three depth-first traversal orders

A traversal names the moment at which the node is processed:

  • pre-order: node, left, right; useful when copying a tree;
  • in-order: left, node, right; outputs BST keys in sorted order;
  • post-order: left, right, node; processes children before their parent.

For the displayed tree, the first three in-order outputs are 20, 30, 40. Keep the recursive call order visible instead of guessing from the drawing.

Written answer8 marks

Give the complete pre-order, in-order and post-order traversals of the displayed BST. Then state which order produces sorted output and why.

Use every node exactly once in each order.

Students type their answer here.

Guided practice

Trace search for 40 and absent 55. Insert 55. Remove leaf 20. After each, write comparison path and redraw only changed links.

Written answer5 marks

Using the displayed tree, give comparison paths for search 40 and 55, then state where 55 would be inserted.

Follow smaller-left/larger-right.

Students type their answer here.

Independent transfer: BST search

Nodes are nested dictionaries with keys value, left and right; missing child is None. Return True if target is present.

Coding task5 marks
def bst_search(node, target):
    pass

Independent mutation: insert into a BST

Implement bst_insert(node, target) recursively. A missing subtree becomes a new node dictionary. Keep the existing tree unchanged when target is a duplicate.

Coding task6 marks
def bst_insert(node, target):
    pass
Written answer3 marks

Explain why inserting already sorted data can make an unbalanced BST behave more like a linked list during search.

Link shape to comparisons.

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
In a BST, smaller keys go to the completion 1 and larger keys to the right. Deleting a leaf removes its parent completion 2. A two-child deletion can use the smallest key in the right completion 3. An completion 4 traversal outputs sorted keys. Sorted insertion can make the tree completion 5.

Review your responses

Check every response against its command word and the supplied constraints. Strengthen unsupported answers with accurate method, mechanism, state or contextual consequence before submitting.