Week 04 Tutorial Answers

ADTs, Binary Search Trees

ADTs

A classic problem in computer science is the problem of implementing a queue using two stacks. Consider the following stack ADT interface:

// Creates a new empty stack
Stack StackNew(void);

// Frees all memory allocated to the stack
void StackFree(Stack s);

// Pushes an item onto the stack
void StackPush(Stack s, int item);

// Pops an item from the stack and returns it
// Assumes that the stack is not empty
int StackPop(Stack s);

// Returns the number of items on the stack
int StackSize(Stack s);

Use the stack ADT interface to complete the implementation of the queue ADT below:

#include "Stack.h"

struct queue {
	Stack s1;
	Stack s2;
};

Queue QueueNew(void) {
	Queue q = malloc(sizeof(struct queue));
	q->s1 = StackNew();
	q->s2 = StackNew();
	return q;
}

void QueueFree(Queue q) {
	StackFree(q->s1);
	StackFree(q->s2);
	free(q);
}

void QueueEnqueue(Queue q, int item) {
	// TODO
}

int QueueDequeue(Queue q) {
	// TODO
}

Answer:

Here is a simple (but inefficient) implementation:

void QueueEnqueue(Queue q, int item) {
	StackPush(q->s1, item);
}

int QueueDequeue(Queue q) {
	while (StackSize(q->s1) > 0) {
		int item = StackPop(q->s1);
		StackPush(q->s2, item);
	}

	int dequeuedItem = StackPop(q->s2);
	
	while (StackSize(q->s2) > 0) {
		int item = StackPop(q->s2);
		StackPush(q->s1, item);
	}

	return dequeuedItem;
}

The time complexity of enqueuing is \(O(1)\), but the time complexity of dequeuing is \(O(n)\) where \(n\) is the number of items in the queue. It also only uses stack s2 to hold items temporarily (it is empty at the start and end of each operation).

In a more efficient implementation, dequeue does not move items from s2 back into s1, and keeps subsequently enqueued items in s1 until s2 has been emptied.

void QueueEnqueue(Queue q, int item) {
	StackPush(q->s1, item);
}

int QueueDequeue(Queue q) {
	if (StackSize(q->s2) == 0) {
		while (StackSize(q->s1) > 0) {
			int item = StackPop(q->s1);
			StackPush(q->s2, item);
		}
	}

	int dequeuedItem = StackPop(q->s2);
	return dequeuedItem;
}

Binary Search Trees

For the questions below, use the following data type:

struct node {
	int value;
	struct node *left;
	struct node *right;
};

(Binary Search Trees)

For each of the sequences below
- start from an initially empty binary search tree
- show the tree resulting from inserting values in the order given
1. 4 6 5 2 1 3 7
2. 5 2 3 4 6 1 7
3. 7 6 5 4 3 2 1
Assume new values are always inserted as new leaf nodes.
Answer:
(Binary Search Trees)

Consider the following tree and its values displayed in different output orderings:

What kind of trees have the property that their in-order traversal is the same as their pre-order traversal?

Are there any kinds of trees for which all output orders will be the same?

Answer:

One obvious class of trees with this property is "right-deep" trees. Such trees have no left sub-trees on any node, e.g., ones that are built by inserting keys in ascending order. Essentially, they are linked-lists.

Empty trees and trees with just one node have all output orders the same. If you come up with any other classes that have this property, let me know.

(Binary Search Trees)

Write a recursive function to count the total number of nodes in a tree. Use the following function interface:

int bstNumNodes(struct node *t) { ... }

Answer:

// counts #nodes in a tree
int bstNumNodes(struct node *t) {
	if (t == NULL) {
		return 0;
	} else {
		return 1 + bstNumNodes(t->left) + bstNumNodes(t->right);
	}
}

(Binary Search Trees)

Implement the following function that counts the number of odd values in a tree. Use the following function interface:

int bstCountOdds(struct node *t) { ... }

Answer:

int bstCountOdds(struct node *t) {
	if (t == NULL) {
		return 0;
	} else if (t->value % 2 != 0) {
		return 1 + bstCountOdds(t->left) + bstCountOdds(t->right);
	} else {
		return bstCountOdds(t->left) + bstCountOdds(t->right);
	}
}

(Binary Search Trees)

Implement the following function to count number of internal nodes in a given tree. An internal node is a node with at least one child node. Use the following function interface:

int bstCountInternal(struct node *t) { ... }

Answer:

int bstCountInternal(struct node *t) {
	if (t == NULL) {
		return 0;
	} else if (t->left == NULL && t->right == NULL) {
		return 0;
	} else {
		return 1 + bstCountInternal(t->left) + bstCountInternal(t->right);
	}
}

(Binary Search Trees)

Write a recursive function to compute the height of a tree. The height of a tree is defined as the length of the longest path from the root to a leaf. The path length is a count of the number of links (edges) on the path. The height of an empty tree is -1. Use the following function interface:

int bstHeight(struct node *t) { ... }

Answer:

int bstHeight(struct node *t) {
	if (t == NULL) {
		return -1;
	} else {
		int lh = bstHeight(t->left);
		int rh = bstHeight(t->right);
		if (lh > rh) {
			return lh + 1;
		} else {
			return rh + 1;
		}
	}
}

Using the ternary operator, we can simplify the code like so:

int bstHeight(struct node *t) {
	if (t == NULL) {
		return -1;
	} else {
		int lh = bstHeight(t->left);
		int rh = bstHeight(t->right);
		return 1 + ((lh > rh) ? lh : rh);
	}
}

(Binary Search Trees)

Implement the following function that returns the level of the node containing a given key if such a node exists, otherwise the function returns -1 (when a given key is not in the binary search tree). The level of the root node is zero. Use the following function interface:

int bstNodeLevel(struct node *t, int key) { ... }

Answer:

Recursive solution:

int bstNodeLevel(struct node *t, int key) {
	if (t == NULL) {
		return -1;
	} else if (t->value == key) {
		return 0;
	} else if (key < t->value) {
		int level = bstNodeLevel(t->left, key);
		if (level == -1) return -1;
		return level + 1;
	} else {
		int level = bstNodeLevel(t->right, key);
		if (level == -1) return -1;
		return level + 1;
	}
}

Iterative solution:

int bstNodeLevel(struct node *t, int key) {
	int level = 0;
	struct node *curr = t;

	while (curr != NULL) {
		if (curr->value == key) {
			return level;
		} else if (key < curr->value) {
			curr = curr->left;
		} else {
			curr = curr->right;
		}
		
		level++;
	}

	return -1;
}

(Binary Search Trees)

Implement the following function that counts the number of values that are greater than a given value. This function should access as few nodes as possible. Use the following function interface:

int bstCountGreater(struct node *t, int val) { ... }

Answer:

int bstCountGreater(struct node *t, int val) {
	if (t == NULL) {
		return 0;
	} else if (t->value > val) {
		return 1 + bstCountGreater(t->left, val) + bstCountGreater(t->right, val);
	} else {
		return bstCountGreater(t->right, val);
	}
}