Week 04 Tutorial Questions

ADTs

1. 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
   }
   

Binary Search Trees

For the questions below, use the following data type:

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

1. (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.

2. (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?

3. (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) { ... }
   

4. (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) { ... }
   

5. (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) { ... }
   

6. (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) { ... }
   

7. (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) { ... }
   

8. (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) { ... }