praxis.ibLog in
B4.1 Fundamentals of ADTsB4.1.4

Structures and properties of binary search trees (BSTs)

Explain the structures and properties of binary search trees (BSTs)

AHL≈ 60 minCommand term: ExplainPremium

In this lesson

  • Using the vocabulary of trees: root, parent, child, leaf, subtree, height
  • Explaining the BST ordering property and how it organises data for fast searching
  • Inserting, searching for and deleting keys, and sketching the resulting tree
  • Carrying out in-order, pre-order and post-order traversals
  • Explaining why a balanced tree gives O(log n) searches and a skewed tree O(n)

This lesson is part of Premium

Every topic has one free lesson. Premium unlocks every interactive lesson, the exam-style questions at the end of each one, and the rest of Praxis IB.

Log in or sign upTry the free lesson: B4.1.1 Properties and purpose of ADTs in programming

What's inside

  1. LearnTrees that keep data in order
  2. LabGrow a search tree
  3. LearnDeleting a node
  4. CodeA BST in code
  5. LearnTraversals of the tree 50, 30, 70, 20, 40, 60, 80
  6. CheckQuick check
  7. ExamWorked exam answer
  8. ReviewMistakes examiners see
  9. Exam practiceExam-style questions

Ends with 4 exam-style questions worth 11 marks, with a self-marking markscheme.