Examlet Week 10 (CPSC 221)

Problem 1

After completing all three removals, the parent of the node containing 97 is:

[x] 42
[ ] 8
[ ] 19
[ ] 17
[ ] 67
[ ] 53
[ ] Empty

Problem 2

Your friend is distraught. They need an inOrder traversal of their binary search tree, but they can't find it anywhere. All they have is the history of transactions: they built the tree by inserting the following keys, in the order given:

Then, they removed the following keys, in the order given:

Can you help your friend? Give the inOrder traversal of your friend's BST by placing the keys in the boxes:

Problem 3

We have inserted a new node into the AVL Tree below, but we have not yet restored its balance.

Please answer the following questions, noting that the names of the options with double rotations describe the order in which the rotations are performed as described in class:

Which node was inserted? 90

Which is the lowest critically unbalanced node? 68

Which rotation will repair the imbalance?

[x] RotateLeft
[ ] RotateLeftRight
[ ] RotateRight
[ ] RotateRightLeft

Problem 4

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.

Options:

What is the runtime to determine if a perfect tree of nodes is an AVL tree?

Time to determine the number of keys in an AVL tree with height that are divisible by (key % == 0).

Maximum number of leaves in an AVL tree of height .

Maximum number of nodes in an AVL tree of height .

Problem 5

Suppose the root of an AVL tree of height 8 has a height balance of 1. What is the maximum number of nodes in the shortest subtree which is a child of the root?

Problem 6

In class we have learned that rotation can be applied to binary (search) trees to change their structure while preserving the in-order key sequence.

In this question, we explore a way to transform any binary search tree into a very specific shape that we call a spine.

Consider a binary search tree with a node definition below:

class BSTNode {
  public:
    int data;
    BSTNode* left;
    BSTNode* right;

    // and a constructor - you do not need to know the details
};

A BST class using the node definition above has a single private member attribute: root.

class BST {
  private:
    BSTNode* root;

  // and private and public member functions
};

A left spine is a binary tree in which there is a single leaf node, and every non-leaf node has only one left child. In this part of the question, complete the MakeLeftSpine function, which receives as a parameter a BSTNode pointer representing the root of some subtree, and transforms the subtree rooted at the parameter node into a left spine and returns the root of the transformed subtree.

To support your implementation, you have at your disposal the following private BST member functions:

// Performs a right rotation around nd and returns the root of the rotated subtree
BSTNode* RotateRight(BSTNode* nd);

// Performs a left rotation around nd and returns the root of the rotated subtree
BSTNode* RotateLeft(BSTNode* nd);

Both recursive and iterative solutions exist without additional helper functions. You are free to choose either implementation.

If your test cases show "NO OUTPUT" or incomplete output, it is likely that your code is producing a segmentation fault. Trace your code on a very small tree to identify where your error may be occurring.

How to Read the Tree Output

The entire tree is rotated counter-clockwise by 90 degrees, so that the root is on the left, and its left subtree is towards the bottom and its right subtree is towards the top. There is one key printed on each line, and each key's amount of indentation indicates the key's depth.

Once again, significant partial credit can be obtained by passing the first test cases: empty, one node, two nodes, three nodes.

For interest (but don't waste too much time reading this) - Since any binary search tree containing nodes can be transformed using only rotations into a left spine, and any sequence of rotations can be reversed, proves that any binary search tree containing nodes can be transformed into any other binary search tree structure containing the same keys. Furthermore, the number of rotations needed to achieve this is bounded by .

/**
 *  File: makeleftspine.cpp
 *  Description: Contains student-implemented functions for transforming
 *               a BST into a left spine
 */

#include <cstddef> // for NULL, if needed
#include "bst.h"
/*** NO OTHER INCLUDES ARE ALLOWED ***/

// Transforms the subtree rooted at nd into a left spine and returns the root of the left spine
BSTNode* BST::MakeLeftSpine(BSTNode* nd) {
    if (nd == NULL) return nd;
    
    if (nd->right != NULL) {
        return MakeLeftSpine(RotateLeft(nd));
    }
    
    if (nd->left == NULL) return nd;
    
    nd->left = MakeLeftSpine(nd->left);
    
    return nd;
}