IB Computer Science HL · Year 2 · Lesson 25
Binary search trees: structure and insertion
Abstract data types separate what operations mean from how they are implemented, helping you choose structures by behaviour and trade-offs.
Paper 250 minutesB4.1.4
Use Next or the arrow keys.
Today’s targets
What you need to be able to do
2 / 8
- ExplainThe structures and properties of BSTs
B4.1.4
Paper 2 lensMatch the depth of every response to the command term. Previously learned content can move quickly, but retrieval must still be accurate.
Page 2 of 8
Retrieve
Rapid Recall Deck
3 / 8
Say the answer aloud before flipping. Mark secure knowledge quickly and spend time on the gaps.
- What ordering property defines a binary search tree (BST)?: For each node, values in the left subtree are ordered before/smaller than the node and values in the right subtree are ordered after/larger than the node, according to the chosen ordering rule.
- What is the root of a BST?: The top node from which all other nodes in the tree descend.
- What is a leaf node?: A node with no child nodes.
- How is a new value inserted into a BST?: Compare from the root, move left or right according to the ordering rule, and place the new node at the first available position.
- Why can a BST support efficient searching?: Each comparison can eliminate an entire subtree when the tree remains reasonably balanced.
Page 3 of 8
B4.1.4 · Learn
Core knowledge and application
4 / 8
B4.1.4Explain
The structures and properties of BSTs
Abstract data types separate what operations mean from how they are implemented, helping you choose structures by behaviour and trade-offs.
Exam moveGive the mechanism or relationship and make the reasons/causes explicit.
Required detail 1How binary search trees (BSTs) are used for data organization
Required detail 2Insert, delete, traverse and searching nodes in a BST
Required detail 3Sketching a BST as a tree diagram
Assessment boundaryPaper 2
Explain it without notes
Explain: The structures and properties of BSTs in the context of a system that needs efficient insertion, search and set membership.
- How binary search trees (BSTs) are used for data organization
- Insert, delete, traverse and searching nodes in a BST
- Sketching a BST as a tree diagram
Page 4 of 8
Worked example · B4.1.4
Binary search tree: organize, insert, search and traverse
5 / 8
Insert: 50, 30, 70, 20, 40, 60, 80
50
/ \
30 70
/ \ / \
20 40 60 80
Search for 60
60 > 50 → go right. 60 < 70 → go left. Match 60.
In-order traversal
Left → node → right produces 20, 30, 40, 50, 60, 70, 80.
Delete reasoningA leaf can be removed directly. A node with one child can be bypassed. A node with two children requires a replacement such as its in-order successor/predecessor while preserving the BST ordering property.
Page 5 of 8
Apply
Transfer to a new scenario
6 / 8
ScenarioA system that needs efficient insertion, search and set membership needs a design or technical decision related to today’s topic. Explain what matters and why.
- How binary search trees (BSTs) are used for data organization
- Insert, delete, traverse and searching nodes in a BST
Page 6 of 8
Exam lens
Paper 2 practice
7 / 8
Build the response before checking notesUse precise terminology and match the required depth.
- Explain: The structures and properties of BSTs in the context of a system that needs efficient insertion, search and set membership.
Self-checkAnswer the exact command term. For explain, include mechanism/reason; for compare, pair criteria; for discuss/evaluate/justify, build supported reasoning and a conclusion.
Page 7 of 8
Homework
Finish the learning cycle
8 / 8
IA — main task
Continue Criterion D development. Keep code readable, record meaningful implementation decisions, and maintain testing/evidence notes as you work.
Syllabus — short
Complete one targeted Paper 2/Paper 1 retrieval task from today’s lesson.
Designed by David Xu
© 2026 David Xu. All rights reserved.
Educators and students are welcome to use these materials for non-commercial teaching and learning with attribution. Please share the original link when possible. Reposting, redistributing modified copies, removing attribution, or commercial use requires prior permission.
End of Lesson 25.