Problem 1

Choose the appropriate running time from the list below.

The variable represents the number of items (keys, data, or key/data pairs) in the structure. In answering this question you should assume the best possible implementation given the constraints, and also assume that every array is sufficiently large to handle all items (unless otherwise stated).

Perform a post-order traversal of a Binary Tree.

• [ ] (a)
• [ ] (b)
• [ ] (c)
• [ ] (d)
• [x] (e)

Problem 2

Recently, your TA team has had a bit of wanderlust. They've written down a few places they'd like to go, and, as all TAs do, chosen one and created a binary tree! They're too busy daydreaming to write down all of its traversals, so they need your help.

Given the following binary tree, provide all four traversals. Your solution should contain only letters -- no commas or brackets!

• Level Order: RKKAAIOK
• In-Order: KAKARIKO
• Post-Order: KAAKIOKR
• Pre-Order: RKAKAKIO

Problem 3

Consider the binary tree class described in lecture where we have 1) variable root that is the treeNode pointer representing the root of the binary tree and 2) each treeNode consists of an integer data element, and two treeNode pointers called left and right.

int fun (treeNode* curr) {
	if (curr != NULL) {
		ret1 = fun(curr->right);
		ret2 = fun(curr->left);
		
		return 1 + max(ret1, ret2);
	}
	else return -1;
}

What does fun(root) return?

• [ ] (a) fun returns the number of elements in the tree.
• [ ] (b) fun returns the shortest distance from root to leaf.
• [ ] (c) None of the other options is correct.
• [x] (d) fun returns the height of the tree.
• [ ] (e) fun returns the sum of all elements in the tree.

Problem 4

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

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

Given the following In-Order and Post-Order traversals of a binary tree:

• In-Order: K N D H L O C M
• Post-Order: N K D L C M O H

find the Pre-Order and Level-Order traversal.

• Pre-Order: HDKNOLMC
• Level-Order: HDOKLMNC

Problem 5

Choose the appropriate worst-case expression from the list below.

The variable represents the number of items (keys, data, or key/data pairs) in the tree and represents the height of the tree. In answering this question you should assume the best possible implementation given the constraints, and also assume that every array is sufficiently large to handle all items (unless otherwise stated).

In a perfect binary tree, what is the length of the longest path from an arbitrary node down to a descendant leaf?

• [ ] (a)
• [ ] (b) None of the options is correct
• [ ] (c)
• [x] (d)
• [ ] (e)

Problem 6

Consider this binary tree Node structure:

struct Node {
  int key;
  int value;
  Node *left, *right;
  Node(int key_, int value_ = 0, Node *left_ = nullptr, Node *right_ = nullptr) : 
    key(key_), value(value_), left(left_), right(right_) {}
};

Complete the function void waldo(Node *¤t) below. current is part of (and maybe the overall root of) a binary tree in which there are no duplicate keys and no duplicate values. waldo performs pre-order traversal of current's subtree, where the action in the traversal is: Check if the current node has a non-null left child whose value is smaller than the current node's value and, if so, swap the positions of the two nodes in the tree.

NOTE:

• "Swapping the positions" of two nodes has a similar effect to just swapping the keys/values within the nodes, in that it leaves the overall shape of the tree unchanged after the swap. HOWEVER, you must accomplish the swap by manipulating the two nodes' left and right pointers and the left/right pointers of their parents (if any) and NOT by directly swapping the keys/values within the nodes.
• We urge you to sketch an example of the swap on paper before implementing!
• current is passed by reference. If it ends up being reassigned, be sure to update the reference!
• For each recursive call in the traversal, use the current node's most up-to-date child pointers (even if the swapping process might cause some nodes to be visited multiple times or not visited at all).

#include <cstdlib> // in case you need the absolute value function abs
#include <cstddef> // for NULL
#include "problem.h"

void waldo(Node *&current) {
    if (current == NULL) return;
    
    if (current->left != NULL && current->left->value < current->value) {
        Node *tempLeft = current->left->left;
        Node *tempRight = current->left->right;
        
        current->left->left = current;
        current->left->right = current->right;
        
        Node *tempCurrent = current->left;
        
        current->left = tempLeft;
        current->right = tempRight;
        
        current = tempCurrent;
    }
    
    waldo(current->left);
    waldo(current->right);
}