Course Notes, Practice Problems, and Solutions
Week 2: Binary search trees, Priority queues and Heaps
Binary Search Trees (CSS 501 notes)
Priority Queues and Heaps
Sample Execution trees
Execution trees (or call trees) show execution of recursive code.
Because recursive problem solving and how the code actually works are
so different, it helps to practice this to get a deeper understanding.
Aim to show the simplest representation so the calls and returns are
easy to see. Typically the parameters and/or local variable values are shown
at each call.
In the first example, the line of code with the recursive call is shown.
In the second example, there was no clean way to show it, so the lines
are numbered. I could have used M C M to represent the three lines
(M for moveDisks and C for cout). In the tree example, typically I use
L and R to represent the recursive calls to the left and right subtrees.
When there is a return value, it is shown on the return arrow.
Supplementary material
Video (from 501, mycodeshool):
Binary Search Trees
Video (from 501, mycodeshool):
C++ implementation
Video (from 501, mycodeshool):
Delete from Binary Search Tree
Video (WeTeach_CS):
MinHeap, insert and remove
I could not find a linear minheap video, so this shows linear time building,
but for a maxheap. A maxheap is similar to a minheap, but parents are
always bigger than their children.
Video (Algorithms with Attitude):
Building a maxheap in linear time
Video (Algorithms with Attitude):
Heapsort using maxheap
Practice Problems
Heap problems
..................
solution
Count the nodes at level n in a binary tree (root is at level zero).
Sample main:
BinTree T;
T.buildTree(...);
cout << T.numNodesAtLevel(4) << endl;
.............. solution
Count the number of nodes that only have one child. Sample main:
BinTree T;
T.buildTree(...);
int count = T.getOnlyChildrenCount();
.............. solution
Now draw an execution tree for a
sample tree ..............
Execution tree