/ Old Curriculum (2014) / Trees - Lesson 2

Trees

IB Computer Science HL

Lesson 2: Walking and Changing Trees

Master the logic of tree traversals and learn the rules for adding and removing nodes from a Binary Search Tree (BST).

Lesson Objectives

  • State the correct output for preorder, inorder, and postorder traversals.
  • Sketch the resulting binary tree after adding a new node.
  • Sketch the resulting binary tree after removing various types of nodes.
↓ Next Activity

What is Tree Traversal?

(15 minutes)

Traversal is a process for visiting every node in a tree exactly once in a specific, predictable order. The name tells you when you "visit" the node relative to its children.

PREorder

(NLR)

1. Visit Node
2. Go Left
3. Go Right

INorder

(LNR)

1. Go Left
2. Visit Node
3. Go Right

POSTorder

(LRN)

1. Go Left
2. Go Right
3. Visit Node

↓ Next Activity

Interactive Traversal Walk

(20 minutes)

50
30
70
20
40
80

Result

↓ Next Activity

Whiteboard Sketching

(30 minutes)

Let's practice modifying the tree. For each prompt, sketch the resulting tree, then click the button to check your answer.

1. Add a Node

Add `60` to the original tree.

2. Remove a Leaf

From the original tree, remove `20`.

3. Remove Node (1 Child)

First, add `10`. Then, remove `20`.

Rule: Parent adopts the grandchild.

4. Remove Node (2 Children)

From the original tree, remove `30`.

Rule: Replace with smallest node from right subtree (the inorder successor).

↓ Next Activity

Exit Ticket: Practice

(5-10 minutes)

25 15 50 20

Using the tree diagram, answer the following:

  1. State the preorder traversal.
  2. State the inorder traversal.
  3. Sketch the tree after adding `10`.
  4. Sketch the tree after removing `25` (from original).
↑ Back to Top