Week 04 Lab Exercise

Binary Search Trees

Objectives

  • To explore the implementation of binary search trees
  • To get some practice with binary search trees
  • To get some practice with time complexity analysis

Admin

Marks
5 (see the Assessment section for more details)
How to submit
see the Submission section
Deadline to submit
12pm Monday of Week 5
Submission late penalty
0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted
When to get handmarked
in your Week 4, 5 or 7 lab session (after you have submitted)
Note: You must get your work handmarked to receive marks for the lab. If you do not get your work handmarked, you will receive 0 marks for the entire lab exercise, regardless of your automarking result.

Click here to request handmarking

Note that you must be physically present in the lab to get handmarked, and you must be prepared to explain your work. During handmarking, if you take too long to explain your work or recall what you did, you may be moved to the end of the queue.

Background

In lectures, we introduced the binary search tree data type and implemented some operations on it. In this week's lab, we will implement some additional operations on it.

Recall that a binary search tree is an ordered binary tree with the following properties:

  • the tree consists of a (possibly empty) collection of linked nodes
  • each node contains a single integer value, and has links to two subtrees
  • either or both subtrees of a given node may be empty
  • all values in a node's left subtree will be less than the value in the node
  • all values in a node's right subtree will be greater than the value in the node
Note: Unless stated otherwise, you are allowed to use any approach for the tasks in this lab. Both iterative and recursive solutions are allowed.

Setting Up

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/26T3/labs/week04/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then unzip the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile
a set of dependencies used to control compilation
bst.h
interface to the BST module
bst.c
implementation of the BST module (incomplete)
Queue.h
interface to the Queue ADT
Queue.c
implementation of the Queue ADT (complete)
Stack.h
interface to the Stack ADT
Stack.c
implementation of the Stack ADT (complete)
runBst.c
interactive test program for the BST module
numCommonValues.c
a program for implementing and testing numCommonValues (incomplete)
analysis.txt
a template for you to enter your time complexity analysis

Once you've got these files, the first thing to do is to run the command

make

This will compile the initial version of the files, and produce the ./runBst and ./numCommonValues executables.

File Walkthrough

runBst.c

This program allows you to test the BST module interactively by entering commands in the terminal. Here is an example run of the program once all the tasks have been completed:

./runBst
Interactive BST Tester
Enter ? to see the list of commands.
> + 6 8 4 1 9 3 5
Inserted 6
Inserted 8
Inserted 4
Inserted 1
Inserted 9
Inserted 3
Inserted 5
> p
    6
   / \
  4   8
 / \   \
1   5   9
 \
  3
> e
The sum of even values is 18
> l
The BST contains 3 leaves
> r
The range of the BST is 8
> P
Pre-order traversal: 6 4 1 3 5 8 9 
> L
Level-order traversal: 6 4 8 1 5 9 3
> d
Deleted all the leaves in the BST
> p
    6
   / \
  4   8
 /
1
> c 3
Closest value to 3 in the BST: 4
> L
Level-order traversal: 6 4 8 1 
> d
Deleted all the leaves in the BST
> p
  6
 /
4
> d
Deleted all the leaves in the BST
> p
6
> q
bst.c

This file contains functions related to creating, querying and manipulating BSTs. Most of these functions are complete, and the rest of the functions need to be implemented in the tasks below.

Queue.h

Queue.h defines the interface to the Queue ADT. The Queue ADT is currently unused, but you will be using it in one of the tasks below.

Task 1 - Sum Even Values in a BST

Your task is to implement this function in bst.c:

int bstSumEvens(struct node *t);

This function should return the sum of all the even values in the given BST.

For example, consider the following BST:

Given the above BST, the function should return \(70\), because the sum of even values in the BST is \(4 + 16 + 24 + 26 = 70\).

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

No time complexity analysis is required for this task.

Task 2 - Count Leaves in a BST

Your task is to implement this function in bst.c:

int bstNumLeaves(struct node *t);

This function should return the number of leaf nodes in the given BST. A leaf node is a node that has no child nodes. The following diagram shows some example trees, with the leaf nodes highlighted in red.

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Analysis 🔍

When you're certain that the function works correctly, determine its worst-case time complexity and write it in analysis.txt along with an explanation. The time complexity should be in terms of \(n\) or \(h\), where \(n\) is the number of nodes in the tree and \(h\) is the height of the tree. You should decide which is more appropriate for your implementation.

To decide whether to use \(n\) or \(h\), think about whether your function always traverses the entire tree (regardless of the structure of the tree) or just one or a constant number of branches. If a function only goes down one or a constant number of branches, then its efficiency depends on the height of the tree rather than the total number of nodes.

Task 3 - Find the Range of a BST

Your task is to implement this function in bst.c:

int bstRange(struct node *t);

This function should return the range of the given BST. The range of a BST is the difference between its smallest value and largest value. If the given tree is empty, the function should return -1.

For example, consider the following BST:

Given the above BST, the function should return \(27\), because its smallest value is \(2\), its largest value is \(29\), and thus its range is \(29 - 2 = 27\).

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Analysis 🔍

When you're certain that the function works correctly, determine its worst-case time complexity and write it in analysis.txt along with an explanation. The time complexity should be in terms of \( n \) or \( h \), where \( n \) is the number of nodes in the tree and \( h \) is the height of the tree. You should decide which is more appropriate for your implementation.

Task 4 - Delete the Leaves of a BST

Your task is to implement this function in bst.c:

struct node *bstDeleteLeaves(struct node *t);

This function should delete all the leaf nodes in the given BST and return the root of the updated tree.

For example, consider the following BST:

The BST contains four leaf nodes, so the function should delete all of them so that the BST now looks like this:

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Note: Be careful to avoid memory leaks! Code that causes memory leaks will incur a penalty which is 10% of the marks for this task.

For this task, you can avoid memory leaks by calling free() on each node that you delete.
No time complexity analysis is required for this task.

Task 5 - Find the Closest Value in a BST

Your task is to implement this function in bst.c:

int bstClosest(struct node *t, int value);

This function should return the value in the BST which is closest to the given value. The function can assume the given BST is not empty. If there is more than one closest value, the function may return any of them. For example, consider the following BST:

  • If the given value is 30, then the function should return 30, because the closest value to 30 in the BST is 30.
  • If the given value is 15, then the function should return 18, because the closest value to 15 in the BST is 18.
  • If the given value is 7, then the function should return 3 or 11, because the closest values to 7 in the BST are 3 or 11 and they are equally close to 7.
Hint: You may find the abs function (provided by stdlib.h) useful.
Note: To get full marks for this task, your function must have a worst-case time complexity of \(O(h)\), where \(h\) is the height of the BST. A solution which is slower than \(O(h)\) can earn at most half of the marks for this task.

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

No time complexity analysis is required for this task.

Task 6 - Level-Order Traversal of a BST

Your task is to implement this function in bst.c:

void bstLevelOrder(struct node *t);

This function should print the level-order traversal of the given BST on a single line separated by spaces (i.e., the same format as the other traverse-and-print functions). The following diagram aims to give an idea of how level-order traversal scans the nodes in a tree:

The output from this traversal would be: 5 3 7 2 4 6 9 1 8.

Level-order traversal cannot be done recursively (at least not easily) and is typically implemented using a queue. The algorithm is roughly as follows:

Level Order Traversal:
	Input: bst t

	create an empty queue
	add the root node of t to the queue
	while the queue is not empty:
		remove the node at the front of the queue
		print the value in the node
		add the node's left child (if any) to the queue
		add the node's right child (if any) to the queue

You must implement this algorithm by making use of the Queue ADT provided. Note that the Queue ADT stores pointers (void * is a generic pointer type). This is because you should store node pointers in the queue rather than integers - if the queue stored integers then after dequeuing an integer, there would be no easy way to add its children to the queue.

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Note: Be careful to avoid memory leaks! Code that causes memory leaks will incur a penalty which is 10% of the marks for this task.

Analysis 🔍

When you're certain that the function works correctly, determine its worst-case time complexity and write it in analysis.txt along with an explanation. The time complexity should be in terms of \( n \) or \( h \), where \( n \) is the number of nodes in the tree and \( h \) is the height of the tree. You should decide which is more appropriate for your implementation.

Note: Make sure to include any Queue ADT functions you used in your analysis, because the time complexity of these functions may affect the time complexity of bstLevelOrder!

Task 7 - Delete Nodes Below a Given Depth

Your task is to implement this function in bst.c:

struct node *bstTrim(struct node *t, int depth);

This function should delete all the nodes in the given BST that are below the given depth and return the root of the updated tree. The root node is at depth 0, its children are at depth 1, and so on. If the given depth is -1, all nodes should be deleted.

For example, consider the following BST:

If the given depth is \(2\), the function should delete all nodes below depth 2 so that the BST now looks like so:

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Note: Be careful to avoid memory leaks! Code that causes memory leaks will incur a penalty which is 10% of the marks for this task.
No time complexity analysis is required for this task.

Task 8 - Count Common Values Between Two BSTs

Your task is to implement this function in numCommonValues.c:

int numCommonValues(struct node *t1, struct node *t2);

This function should return the number of common values between the two given BSTs. The function must not use arrays or malloc/calloc, either directly or indirectly.

For example, consider the following BSTs:

Given the above BSTs, the function should return \(3\), because there are three common values between them: \(3\), \(17\) and \(23\).

Once you think you've got the function working, test it by recompiling with make and running the numCommonValues program. The program should behave like so:

./numCommonValues
Enter values to insert in t1: 14 7 3 23 20 17 29
t1:

    14
    / \
   /   \
  7    23
 /     / \
3     /   \
     20   29
    /
   17

Enter values to insert in t2: 17 3 2 16 23 26 24
t2:

    17
    / \
   /   \
  3    23
 / \     \
2  16    26
         /
        24

Number of common values: 3
Note: Arrays and malloc/calloc are forbidden in this task. Solutions that use arrays or malloc/calloc will not receive any marks.

Analysis 🔍

When you're certain that the function works correctly, determine its worst-case time complexity and write it in analysis.txt along with an explanation. The time complexity should be in terms of one or more of the following: \( n _1\) (the number of nodes in t1), \( h_1 \) (the height of t1), \( n_2 \) (the number of nodes in t2), and \(h_2\) (the height of t2).

Hints

Please give the task at least 10 minutes of thought before looking at these hints!

Here is a simple way to solve this problem:

For each value in one of the BSTs (say t1), check if the value exists in the other BST (t2)

Think about how you could implement this (and try implementing it) before looking at the next hint!

This problem is similar to the bstCountOdds tutorial question, but instead of counting the number of values that are odd, we need to count the number of values that exist in the other BST. This means you can solve this problem by following the same structure as bstCountOdds.

Try implementing this before looking at the next hint!

Could you implement a helper function to check if a BST contains a value? Better yet, is there a function provided in bst.h that you can use?

The previous hints suggest that we need to recurse through one of the BSTs (say t1) to check if each of its values exists in the other BST (t2). When you recurse, you should simply pass down the root node of t2 instead of t2->left or t2->right, because the value you need to check could be anywhere in t2.

Optional Challenge Task - Iterative Pre-Order Traversal of a BST

Note: This task is optional. It is not worth any marks.

Pre-order traversal is usually implemented recursively, but it can also be implemented iteratively, using a stack!

Your task is to implement the following function in bst.c:

void bstIterativePreOrder(struct node *t);

This function should print the pre-order traversal of the given BST on a single line separated by spaces (i.e., the same format as the other traverse-and-print functions). The function must not use recursion.

Once you think you've got the function working, test it by recompiling with make and running the runBst program.

Submission

Submit via the command line using the give command:

give cs2521 lab04 bst.c numCommonValues.c analysis.txt

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Assessment

Mark Breakdown

Aspect Marks Description
Code correctness 4 Your code for each task will be automarked. Automarking will be run after submissions have closed. After automarking is run you will be able to view your results here.
Complexity analysis 1 Your tutor will check that you have completed the time complexity analysis for each of the required functions in analysis.txt and ask you to re-explain your analysis for each function. Analysis of each function is worth 0.25 marks.

Note that you should be prepared to explain your analysis without reading from analysis.txt, but your written explanation should still be thorough. We have provided some advice for writing a thorough time complexity analysis below.

Complexity Analysis Guidelines

Your time complexity analysis should be thorough and cover all parts of a function (except possibly simple \(O(1)\) edge cases). This includes:

  • Loops - Your analysis should acknowledge the number of iterations of the loop and the time complexity of the loop body (unless the loop body is very simple)
  • Recursion - Your analysis should acknowledge the number of recursive calls performed by the function, as well as the amount of work done per recursive call (not including the recursion itself)
  • Other functions - You should analyse the time complexity of any function used by the main function you are analysing, including functions that you did not write yourself. If the time complexity of a function is given (e.g., in a header file), you do not need to explain the time complexity, but you must still mention it.