Start learning →

Trees and heaps

Structures that branch: binary trees and their traversals, search trees that keep keys in order, and heaps that always know their smallest item.

About 8 hours of study

Learning objectives

Lessons

  1. 1

    Binary trees

    Nodes with left and right children, preorder, inorder and postorder traversal, and recursive height and count.

  2. 2

    Binary search trees

    Smaller keys to the left, larger to the right: insert, search, and delete with its three cases.

  3. 3

    Heaps and priority queues

    A complete binary tree stored in an array: push with sift-up, pop the minimum with sift-down, and build a heap in O(n).

Module practice

Module quiz

1. Which traversal visits the root of a binary tree last?
2. Where is the smallest item of a min-heap?
3. Keys 40, 20, 60, 10 and 30 are inserted into an empty binary search tree. What is its preorder traversal?
4. A heap is stored in an array from index 0. Where are the children of the item at index 4?
5. A node with two children is deleted from a binary search tree. Which key can take its place?
6. The smallest item is popped from the min-heap [2, 5, 3, 9, 6]. What is the array afterwards?
7. A binary search tree holds 1,000 keys. What are the smallest and largest heights it can have, counting levels?

‹ Stacks and queuesHash tables and graphs ›