Week 04 Lab Solution

Binary Search Trees

Sample Solution

`bstNumLeaves()`

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

Worst case time complexity: \( O(n) \)

Explanation: The number of operations performed within each function call (ignoring recursion) is constant, and at most \( 2n \) calls to the function are made, so the worst case time complexity must be \( O(n) \).

`bstRange()`

int bstRange(struct node *t) {
	if (t == NULL) {
		return -1;
	}

	struct node *currMin = t;
	while (currMin->left != NULL) {
		currMin = currMin->left;
	}

	struct node *currMax = t;
	while (currMax->right != NULL) {
		currMax = currMax->right;
	}

	return currMax->value - currMin->value;
}

Worst case time complexity: \( O(h) \)

Explanation: Each while loop goes down one branch of the tree, and the length of a branch is at most \( h \), where \( h \) is the height of the tree. Therefore, the worst case time complexity is \( O(h) \).

`bstDeleteLeaves()`

struct node *bstDeleteLeaves(struct node *t) {
	if (t == NULL) {
		return NULL;
	} else if (t->left == NULL && t->right == NULL) {
		free(t);
		return NULL;
	} else {
		t->left = bstDeleteLeaves(t->left);
		t->right = bstDeleteLeaves(t->right);
		return t;
	}
}

Worst case time complexity: \( O(n) \)

Explanation: Assuming that free() is \( O(1) \), the number of operations performed within each function call (ignoring recursion) is constant. At most \( 2n \) calls to the function are made, so the worst case time complexity must be \( O(n) \).

`bstClosest()`

int bstClosest(struct node *t, int val) {
	assert(t != NULL);

	int closestInSubtree = t->value;

	if (t->value < val && t->right != NULL) {
		closestInSubtree = bstClosest(t->right, val);
	} else if (t->value > val && t->left != NULL) {
		closestInSubtree = bstClosest(t->left, val);
	} else {
		return t->value;
	}

	if (abs(t->value - val) < abs(closestInSubtree - val)) {
		return t->value;
	} else {
		return closestInSubtree;
	}
}

`bstLevelOrder()`

void bstLevelOrder(struct node *t) {
	if (t == NULL) {
		return;
	}
	
	Queue q = QueueNew();
	QueueEnqueue(q, t);
	while (!QueueIsEmpty(q)) {
		struct node *n = QueueDequeue(q);
		showBstNode(n);
		if (n->left != NULL) {
			QueueEnqueue(q, n->left);
		}
		if (n->right != NULL) {
			QueueEnqueue(q, n->right);
		}
	}
	QueueFree(q);
}

Worst case time complexity: \( O(n) \)

Explanation: Note that enqueuing and dequeuing are \( O(1) \) operations due to the specific implementation of the queue. Thus, the operations within the while loop are \( O(1) \), which means that the complexity is determined by the number of iterations of the loop. The number of iterations is \( n \), since every tree node is enqueued once, and one node is dequeued every iteration. So the complexity is \( O(n) \).