Week 04 Lab Exercise

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

int bstNumLeaves(struct node *t);

This function should return a count of 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 sample 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.

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.

Your task is to implement the following 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:

The range of this BST is 27, because the largest value is 30, the smallest value is 3, and \( 30 - 3 = 27 \).

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

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.

Your task is to implement the following 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. The following diagram shows the result of repeatedly applying the function to a sample tree.

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

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.

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

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

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.

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

Your task is to implement the following 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(BST t):
	initialise an empty queue
	add t's root node to the queue
	while the queue is not empty do
		remove node x from the front of the queue
		print the value in x
		add the left child (if any) of x to the queue
		add the right child (if any) of x to the queue
	end while

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.

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.

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.

Your solution must use the provided Stack ADT.

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