Week 04 Tutorial Answers

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;

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

    Answer:

    Node listFilterR(Node, FilterFunc);

void listFilter(List l, FilterFunc fp) {
    l->head = listFilterR(l->head, fp);
}

Node listFilterR(Node n, FilterFunc fp) {
    if (!n)
        return NULL;

    int delete = !fp(n->value);
    Node rest = listFilterR(n->next, fp);
    if (delete) {
        free(n);
        return rest;
    } else {
        n->next = rest;
        return n;
    }
}

  2. (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);

    Answer:

    int listReduceR(Node n, ReduceFunc fp, int init);

int listReduce(List l, ReduceFunc fp, int init) {
    return listReduceR(l->head, fp, init);
}

int listReduceR(Node n, ReduceFunc fp, int init) {
    if (!n)
        return init;
    
    int result = listReduceR(n->next, fp, init);
    return fp(result, n->value);
}
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;

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

    Answer:




  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?

    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.

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

    Answer:

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

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

    Answer:

    int BSTreeCountOdds(BSTree t) {
	if (t == NULL) {
		return 0;
	} else if (t->value % 2 != 0) {
		return 1 + BSTreeCountOdds(t->left) + BSTreeCountOdds(t->right);
	} else {
		return BSTreeCountOdds(t->left) + BSTreeCountOdds(t->right);
	}
}

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

    Answer:

    int BSTreeHeight(BSTree t) {
	if (t == NULL) {
		return 0;
	} else if (t->left == NULL && t->right == NULL) {
		return 0;
	} else {
		int lh = BSTreeHeight(t->left);
		int rh = BSTreeHeight(t->right);
		return 1 + ((lh > rh) ? lh : rh);
	}
}

    If we take the height of an empty tree to be -1, then we can simply the function as follows:

    int BSTreeHeight(BSTree t) {
	if (t == NULL) {
		return -1;
	} else {
		int lh = BSTreeHeight(t->left);
		int rh = BSTreeHeight(t->right);
		return 1 + ((lh > rh) ? lh : rh);
	}
}

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

    Answer:

    int BSTreeCountInternal(BSTree t) {
	if (t == NULL) {
		return 0;
	} else if (t->left == NULL && t->right == NULL) {
		return 0;
	} else {
		int l = BSTreeCountInternal(t->left);
		int r = BSTreeCountInternal(t->right);
		return 1 + l + r;
	}
}

  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 BSTreeNodeLevel(BSTree t, int key) { ... }

    Answer:

    int BSTreeNodeLevel(BSTree t, int key) {
	if (t == NULL) {
		return -1;
	} else if (t->value == key) {
		return 0;
	} else if (key < t->value) {
		int ndl = BSTreeNodeLevel(t->left, key);
		if (ndl == -1) return -1;
		return ndl + 1;
	} else {
		int ndr = BSTreeNodeLevel(t->right, key);
		if (ndr == -1) return -1;
		return ndr + 1;
	}
}

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

    Answer:

    int BSTreeCountGreater(BSTree t, int val) {
	if (t == NULL) {
		return 0;
	} else if (t->value > val) {
		return 1 + BSTreeCountGreater(t->left, val) + BSTreeCountGreater(t->right, val);
	} else {
		return BSTreeCountGreater(t->right, val);
	}
}

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

    Answer:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    int isHeightBalanced(BSTree t) {
	if (t == NULL) return -1;
 
	int hl = isHeightBalanced(t->left);
	int hr = isHeightBalanced(t->right);
 
	// at least one of the subtrees is not height balanced
	if (hl == NOT_HEIGHT_BALANCED || hr == NOT_HEIGHT_BALANCED)
		return NOT_HEIGHT_BALANCED;
 
	int diff = hl - hr;
	// absolute diff is more than one, so not height balanced
	if (diff < -1 || diff > 1)
		return NOT_HEIGHT_BALANCED;
 
	// so far the tree is height balanced; return height
    return (hl > hr ? hl : hr) + 1;
}

  10. 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.

    Answer:

    After right rotation on node containing 10:

    After left rotation on node containing 6:

  11. Show the sequence of rotations that would be required to move the node containing the 7 to the root of this binary tree:

    Answer: