← IB Computer Science

Trees and traversals

Topic B4 is Higher Level only. This unit covers binary trees and, in particular, the binary search tree (BST), an ADT that keeps data sorted so it can be searched quickly. You need the terminology (root, parent, child, leaf, subtree), the left and right ordering rules, how to insert values and sketch the resulting tree, and the three traversal orders. Traversals are the highest-risk part, so work them out node by node.

Slide 1 / 4

Binary trees and BST terminology

Binary search tree terminology 50 30 70 20 40 80 root parent leafleafleaf left subtree of 50 Ordering rule Left subtree keysare less than the node. Right subtree keysare greater than node. 20 < 30 < 40 < 50 < 70 < 80 so the BST keeps data sorted
  • A tree stores data in nodes arranged in a hierarchy. A binary tree is a tree in which each node has at most two children: a left child and a right child.
  • Key terms: the root is the top node from which all others are reached; a parent has children below it; a leaf is a node with no children; a subtree is any node together with all of its descendants.
  • A binary search tree (BST) adds an ordering rule to a binary tree so the data stays sorted.
  • Left child property: every key in a node's left subtree is less than that node. Right child property: every key in its right subtree is greater than that node.

Check you've got it

0/4

1. In a binary search tree, what is a leaf node?

2. An empty BST has 40, 20, 60, 10, 30 inserted in that order. Where is the value 50 placed when it is inserted next?

3. A BST is built by inserting 50, 30, 70, 20, 40, 60, 80 in that order. What is the output of an IN-ORDER traversal?

4. A BST is built by inserting 8, 3, 10, 1, 6 in that order. What is the output of a PRE-ORDER traversal?

Free revision content. Multiple-choice answers are marked instantly. Written answers are marked by AI on /free-mark.