Trees

This week’s section exercises are all about trees, particularly binary search trees and common tree idioms and algorithms. Trees are yet another way to organize the way that data is stored, and they are perhaps one of the most powerful paradigms for data storage that we've encountered so far! Their recursive structure makes writing recursive functions very natural, so we will be using lots of recursion when working with trees. After you're done working through this section handout, you'll truly know what it means to party with trees!

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter project

For all the problems in this handout, assume the following structures have been declared:

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

    // default constructor does not initialize
    TreeNode() {}   

    // 3-arg constructor sets fields from arguments
    TreeNode(int d, TreeNode* l, TreeNode* r) {  
        data = d;
        left = l;
        right = r;
    }
};

You can also assume the following utility functions have been defined as well:

// takes in the pointer to a tree and frees all
// the memory associated with that tree.
void freeTree(TreeNode *node) {
    if (node == nullptr) return;
    freeTree(node->left);
    freeTree(node->right);
    delete node;
}

1. No, You're Out of Order!

Write the elements of each tree below in the order they would be seen by a pre-order, in-order, and post-order traversal.

a)

b)

c)

2. Count Left Nodes (countleft.cpp)

Write a function

that takes in the root of a tree of integers and returns the number of left children in the tree. A left child is a node that appears as the root of a left-hand subtree of another node. For example, the tree in problem 1(a) has 3 left children (the nodes containing 5, 1, and 4).

int countLeftNodes(TreeNode *node) {
    if (node == nullptr) {
        return 0;
    } else if (node->left == nullptr) {
        return countLeftNodes(node->right);
    } else {
        return 1 + countLeftNodes(node->left) + countLeftNodes(node->right);
    }
}

3. Find Your True Balance (balanced.cpp)

Write a function

that takes in the root of a tree of integers and returns whether or not the tree is balanced. A tree is balanced if its left and right subtrees are balanced trees whose heights differ by at most 1. The empty tree is defined to be balanced. You can assume you already have a function that gives you the height of a tree. The signature for this function is:

bool isBalanced(TreeNode *node) {
    /* From the problem statement, an empty tree is balanced */
    if (node == nullptr) {
        return true;
    } else {
    /* From the problem statement, "a tree is balanced if its left and right subtrees are balanced trees whose heights differ by at most 1". The key thing to note is that this is taken right from the problem statement! (even if you didn't understand the question well, we tell you the formula to find whether a tree is balanced or not!) */
        return isBalanced(node->left) && isBalanced(node->right) && 
                abs(height(node->left) - height(node->right)) <= 1;
    }
}

4. Give 'Em The Axe (prune.cpp)

Write a function

that accepts a reference to a pointer to a TreeNode and removes the leaf nodes from a tree. A leaf is a node that has empty left and right subtrees. If t is the tree on the left, removeLeaves(t) should remove the four leaves from the tree (the nodes with data 1, 4, 6, and 0). A second call would eliminate the two new leaves in the tree (the ones with data values 3 and 8). A third call would eliminate the one leaf with data value 9, and a fourth call would leave an empty tree because the previous tree was exactly one leaf node. If your function is called on an empty tree, it does not change the tree because there are no nodes of any kind (leaf or not). You must free the memory for any removed nodes.

void removeLeaves(TreeNode*& node) { 
    if (node != nullptr) { 
        if (node->left == nullptr && node->right == nullptr) { 
            delete node; 
            node = nullptr; // you can do this since node is passed by reference! 
        } else { 
            removeLeaves(node->left); 
            removeLeaves(node->right); 
        } 
    } 
}