Examlet Week 9 (CPSC 221)

Problem 1

It's 1AM, and all through the house, not a creature was stirring... except for your TA. They've been given the Pre-Order traversal of a binary search tree, but they're missing the Level-Order and Post-Order traversals...

they're tired... so tired... and then they realized that they could ask their students to help them out!

Given the following Pre-Order traversal of a binary search tree:

Pre-Order: P E D H G V U W X

find the Level-Order and Post-Order traversals.

For reference, the English alphabet will be ordered with the following relative values:

A < B < C < D < E < F < G < H < I < J < K < L < M < N < O < P < Q < R < S < T < U < V < W < X < Y < Z

Level-Order: PEVDHUWGX
Post-Order: DGHEUXWVP

Problem 2

Build a binary search tree by inserting all of the keys in the array below, in the order given.

The left child of the node containing 87 is:

[ ] 65
[ ] 69
[ ] 3
[ ] 33
[ ] 74
[ ] 45
[ ] 14
[x] Empty

The right child of the node containing 87 is:

[ ] 65
[ ] 69
[ ] 3
[ ] 33
[ ] 74
[ ] 45
[ ] 14
[x] Empty

Problem 3

Which of the following could be the sequence of keys compared in a search for 333 in a binary search tree?

[x] (a) 455, 216, 243, 426, 284, 396
[ ] (b) 263, 382, 431, 238, 491, 378
[ ] (c) 250, 416, 463, 487, 277, 493

Select all possible options that apply.

Problem 4

The Binary Search Tree below has an unknown key X. (The tree contains only keys, no values.)

Answer the following questions. Assume all keys are integers and there are no duplicate keys. (Hence X cannot be the same as any of the other keys in the tree).

What is the minimum value of X?

What is the maximum value of X?

Problem 5

Oh no! Winnie accidentally changes the key 7 in the Binary Search Tree above to 20.

Which of the following operations will fail because of Winnie's change? Assume each operation starts over from Winnie's adjusted BST. (An insert fails if it puts the key in a different spot in Winnie's BST from where it would have gone in the original BST. A find fails if it returns the wrong value. Either operation fails if it causes an error.)

[x] (a) insert(9)
[ ] (b) insert(26)
[ ] (c) find(28)
[ ] (d) find(1)
[x] (e) insert(12)
[x] (f) find(10)

Select all possible options that apply.

Problem 6

Choose the BEST asymptotic description for each of the following statements. Unless otherwise stated, assume we are referring to the worst-case behavior or structure, and that our algorithms (if any) are the best possible for the scenario.

Maximum number of nodes on the path from the root to the largest key in a binary search tree of nodes.

Minimum height of any binary tree with nodes.

Time to remove the root from a perfect binary search tree with nodes (so that the result is a BST).

Problem 7

Consider a Binary Tree (not necessarily a BST) with a node definition as follows:

struct TreeNode {
  int data;
  TreeNode* left;
  TreeNode* right;
};

Two trees can be "mirror images" of one another; that is, two trees may contain the same keys placed such that one is the result of flipping the other horizontally (around a vertical axis). You will write a function to check whether two trees are mirror images of one another.

In the editor below, complete the IsFlip function. HINT: this function should be implemented recursively.

Note: In test output, each tree's contents are output as if they have been "rotated" 90 degrees counter-clockwise so their roots are on the left. There is one node per line. Each line's indentation shows its depth in the tree. The left subtree of a node is printed below it; the right is printed above.

/*
*  File: treeflip.cpp
*  Description: Implementation of a binary tree manipulation for EX6
*/

#include <cstddef>  // For NULL
#include "tree.h"
#include "treeisflip.h"

// Test if two trees are flips of one another (structure and data)
// returns true if nd1 and nd2 are flipped, false otherwise
// See the PrairieLearn page for examples of operation
bool IsFlip(TreeNode* nd1, TreeNode* nd2) {
  if (nd1 == NULL && nd2 == NULL) return true;
  if (nd1 == NULL || nd2 == NULL) return false;
  if (nd1->data != nd2->data) return false;
  
  return (
     IsFlip(nd1->left, nd2->right)
     && IsFlip(nd1->right, nd2->left)
  );
}