B4 Abstract data types (HL)

For the new IB Diploma Computer Science syllabus to start teaching in August 2025, and for first examinations in May 2027.

Unit and lesson overviews will be gradually published as developed.

Lesson 1: Intro to ADT (HL)

  • B4.1.1 Explain the properties and purpose of ADTs in programming.

Lesson 2,3,4: Linked lists (HL)

  • B4.1.2 Evaluate linked lists.
  • B4.1.3 Construct and apply linked lists: singly, doubly and circular.

Exercises

  1. Hackerrank Insert a node at the tail of a linked list
  2. Hackerrank Insert a node at the head of a linked list
  3. Hackerrank Reverse a linked list
  4. Hackerrank Merge two sorted linked lists
  5. Leetcode 83 Remove duplicate nodes from a sorted linked list
  6. Hackerrank Maximum element
  7. Leetcode 141 Linked List Cycle

Lesson 5,6,7: Binary search trees (HL)

  • B4.1.4 Explain the structures and properties of BSTs.

Using a basic binary tree node class as your starting point (such as the one below), add the following methods to your node class.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def inorder(self):
        pass # Implement a method to print an in-order traversal
    def preorder(self):
        pass # Implement a method to print a pre-order traversal
    def postorder(self):
        pass # Implement a method to print a post-order traversal
    def insert(self, value):
        pass # Implement a method to perform a BST insertion
    def delete(self, value):
        pass # Implement a method to perform a deletion that maintains BST order

n = Node(42)

Exercises

  1. Implment the missing methods in the above Node class.
  2. find_min() - Implement a find_min() method that returns the smallest value in a Binary Search Tree.
  3. search(value) - Implement a search() method that returns True if a given value exists in a Binary Search Tree.
  4. Modify insert() - Modify the insert() method so as to have an optional parameter, allow_duplicates that, when set to False will drop (ignore) any attempt to add a value already in the binary tree.
  5. max_depth() - Return the longest path from the root node to the furthest leaf node. Use it to solve Hackerank Tree: Height of a Binary Tree
  6. is_in_order() - Search the contents of the tree and returns True if the contents are sorted for in order traversal. Use it to solve Leetcode 98 Validate Binary Search Tree
  7. reverse() - Reverse the order of the binary tree contents. Use it to solve Leetcode 226 Invert Binary Tree
  8. get_nearest_ancestor(a,b) - Given two nodes (a and b), find the first parent/grandparent/etc that they have in common and return it. Use it to solve Binary Search Tree : Lowest Common Ancestor
  9. Process the input data, placing each value into a binary search tree in the order it is given to you (ie: don’t pre-sort the data). Calculate the maximum depth and the maximum width of the resulting binary search tree. Multiply the maximum depth by the maximum width to find your answer value. CodingQuest 2023 question 9

Lesson 8,9,10: Sets (HL)

  • B4.1.5 Construct and apply sets as an ADT.

Exercises

  1. Hackerrank Set .add()
  2. Hackerrank Mean calculation of unique terms
  3. Leetcode 26 - Remove Duplicates from Sorted Array (You’ve had this question previously - how would you now do it with sets?)
  4. Leetcode 349 Intersection of two arrays
  5. Leetcode 217 Contains duplicate
  6. AoC 2020 Day 6 Customs declaration

Lesson 11,12,13: Hashmaps (HL)

  • B4.1.6 Explain the core principles of ADTs.

Exercises

  1. Leetcode 1 Two sum
  2. Leetcode 242 Valid anagram
  3. Leetcode 387 First unique characeter in a string
  4. Hackerrank Word order
  5. Hackerrank Company logo
  6. Aoc 2021 Day 14 Extended polymerization
  7. Hackerrank Birthday Cake Candles - you’ve had this question previously. How does a hashmap simplify it?

Lesson 14,15,16: Programming scenarios (HL)

Coming soon

Lesson 17,18,19: Exam style questions (HL)

Lesson 20: Assessment (HL)

Copyright © Paul Baumgarten.