Week 04 Tutorial Questions

Function Pointers and Binary Search Trees

Function Pointers

For the function pointer questions below, consider the following definition of the List data structure.

typedef struct node {
    int value;
    struct node *next;
} *Node;

typedef struct list {
    Node head;
} *List;

(Function Pointers)

Implement the following function that takes a linked list and a function pointer and removes all nodes that return 0 when passed through the filter function. Use the following function pointer type, and prototype:
```
typedef int (*FilterFunc)(int);

void listFilter(List l, FilterFunc fp);
```
(Function Pointers)

Implement the following function that takes a linked list and a function pointer and returns the reduction of the list, starting from the end. The function pointer takes the result of the previous calculation and the next item in the list, and produces a value to pass into the next function call. Initially, this value should be init. For example, consider the following invocation:
```
int formNumber(int prev, int curr) {
    return prev * 10 + curr;
}

int main(void) {
    List l; // Pretend this contains numbers 1 to 6.
    int value = listReduce(l, formNumber, 0);
    printf("%d\n", value);
}
```
This program would print 654321.

Use the following function pointer type, and prototype:
```
typedef int (*ReduceFunc)(int, int);

int listReduce(List l, ReduceFunc fp, int init);
```

Binary Search Trees

For the BST questions below, consider the following definition of the BSTree data structure.

typedef struct BSTNode *BSTree;
typedef struct BSTNode {
	int value;
	BSTree left;
	BSTree right;
} BSTNode;

(Binary Search Trees)

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

Write a recursive function to count the total number of nodes in a tree. Use the following function interface:
```
int BSTreeNumNodes(BSTree t) { ... }
```
(Binary Search Trees)

Implement the following function that counts the number of odd values in a tree. Use the following function interface:
```
int BSTreeCountOdds(BSTree t) { ... }
```
(Binary Search Trees)

Write a recursive function to compute the height of a tree. The height 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. Use the following function interface:
```
int BSTreeHeight(BSTree t) { ... }
```
(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 non-empty subtree. Use the following function interface:
```
int BSTreeCountInternal(BSTree t) { ... }
```
(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 BSTreeNodeLevel(BSTree t, int key) { ... }
```
(Binary Search Trees)

Implement the following function that counts the number of values that are greater than a given value. This function should avoid visiting nodes that it doesn't have to visit. Use the following function interface:
```
int BSTreeCountGreater(BSTree t, int val) { ... }
```
Implement the following function that returns the height of a given basic binary tree if it is height-balanced. Otherwise, if the given binary tree is not height-balanced, the function returns NOT_HEIGHT_BALANCED.

Height-balanced tree: We say that a basic binary tree is height-balanced if, for every node, the absolute difference between the height of the left subtree and the height of the right subtree is one or less. In other words, every node needs to satisfy the following criteria: abs(height(left) - height(right)) ≤ 1

Use the following function interface:
```
#define NOT_HEIGHT_BALANCED -99

typedef struct BSTNode *BSTree;
typedef struct BSTNode {
	int value;
	BSTree left;
	BSTree right;
} BSTNode;

int isHeightBalanced(BSTree t) { ... }
```
Show how the following tree would change if we do a right rotation on the node containing 10 followed by a left rotation on the node containing 6.
Show the sequence of rotations that would be required to move the node containing the 7 to the root of this binary tree: