# 16.3. Exercises#

Many of these exercises are taken from past exams of APS105 Computer Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.

Headings in this page classify the exercises into different categories: [Easy], [Intermediate], and [Challenging]. I suggest you start by easy exercises and work your way up to the challenging ones.

Question 12 in Winter 2017 Final Exam[Easy]

Consider the following binary search tree:

This tree may have been created by inserting the elements in the following order: 5, 3, 7, 4, 6.

Or it may have been created by inserting the elements in the following order: 5, 7, 3, 6, 4.

But a different tree would have been created by inserting the elements in the following order: 5, 4, 6, 7, 3.

How many different ways can the elements {3, 4, 5, 6, 7} be inserted into a binary tree so that the same tree is created as in the figure above?

Question 10 in Winter 2018 Final Exam[Easy]

Identify and correct all errors you find in the C program below. Each line may or may not contain errors, and there may be more than one error per line.

 1#include <stdio.h>
2#include <stdlib.h>
3typedef struct node {
4  int data;
5  struct node *left, right;
6} Node;
7Node *insert(Node *root, int item) {
8  if (root == NULL) {
9  }
10  return newNode(item);
11}
12if (item <= (*root).data) insert(root->left, item) return root;
13int main(void) {
14  int list[] = {15, 3, 2};
15  Node *root = NULL;
16  for (int i = 0; i < 13; i++) {
17  }
18  return 0;
19}


Line

Description of error

Correction

Question 10 in Winter 2019 Final Exam[Challenging]

Consider the binary search tree below:

The lowest common ancestor, LCA, of two nodes p and q is either one of the two nodes having the other as a descendant, or the lowest node in the tree that has both p and q as descendants. For example, in the binary search tree above:

• The LCA of nodes 5 and 28 is 22.

• The LCA of nodes 7 and 30 is 29.

• The LCA of nodes 35 and 61 is 35.

• The LCA of nodes 30 and 41 is 35.

Complete the recursive helper function, with the prototype given on the next page, which takes the tree root and two values of node data, and returns the LCA (a node) of the given nodes.

Assume that the two int values provided always exist in the tree.

Assume that the binary search tree is designed as follows:

typedef struct node {
int data;
struct node *left, *right;
} Node;
typedef struct bstree {
Node *root;
} BSTree;


The main function, lca(), uses an auxiliary helper function to perform the task; this helper function is called inside the lca function:

Node *lca(BSTree *tree, int na, int nb) {

}

Node *lcaHelper(Node *p, int na, int nb) {

}


Question 12 in Winter 2019 Final Exam[Challenging]

Complete a recursive helper function and a main calling function to scan an existing binary search tree and create a new tree with only the even values from the first tree. You can use the functions developed in class, including:

void initBSTree(BSTree *tree) { tree->root = NULL; }
bool insert(BSTree *tree, int value); // implemented in previous section


You may assume that the following data structure types have been defined:

typedef struct node {
int data;
struct node *left, *right;
} Node;
typedef struct bstree {
Node *root;
} BSTree;

Node *treeWithEvens(BSTree *inputTree) {

}
bool evensHelper(Node *current, BSTree *evenTree) {
// helper function: check this node and connected nodes using a recursive
// call,
// placing even values in the new tree

}


Question 12 in Winter 2017 Final Exam[Challenging]

Recall that, in a binary tree, a node that has no children is called a leaf. Given the following node declaration:

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


Write a function called treeLeafCount() that takes one struct treeNode *root parameter and returns the number of leaves in the tree pointed to by root. You may not use global variables in your solution.

Question 16 in Winter 2018 Final Exam[Challenging]

The following C structure is used to define each node in a binary search tree:

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


Write a C function:

Node *secondLargestNode(Node *root);


that finds and returns a pointer to the node that contains the second largest value in the binary search tree. The parameter root is a pointer to the root node of a binary search tree. If the binary search tree is empty or has one node only, the function returns NULL. For example, if the function is called with root pointing to the binary search tree in Fig. 16.3, it will return a pointer to the node that contains 6.