Tree Encoding

This week's section focuses on getting practice with a new kind of structure, trees! Trees are very similar in some ways to linked lists, but are structured a little differently. Also, friendly reminder that every week we provide 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;
    }
};

struct TernaryTreeNode {
    char ch;
    TernaryTreeNode *left;
    TernaryTreeNode *middle;
    TernaryTreeNode *right;

    TernaryTreeNode() {}

    TernaryTreeNode(char c) {
        ch = c;
        left = middle = right = nullptr;
    }

    TernaryTreeNode(char c, TernaryTreeNode* l, TernaryTreeNode* m, TernaryTreeNode* r) {
        ch = c;
        left = l;
        middle = m;
        right = r;
    }

    bool isLeaf() {
        return left == nullptr && middle == nullptr && right == nullptr;
    }
};

1. Decode Sequence (ternary.cpp)

We will be using the ternary tree definition above in this problem. A ternary tree is a tree where each node in the tree has at most 3 child nodes (left, middle and right). Each node in this tree, except the root, stores a character. Given a pointer to a ternary tree node and a string representing a sequence of directions , write a function

that returns the string obtained by following the directions in the sequence. For example, in the tree below, a sequence like "RM" gives us the string "XG". As another example, a sequence like "LMR" gives us the string "AT". Notice that, in second example, we can't move right because the middle node with T has no right child. In such cases, you should stop processing the remaining directions and return the string you built so far. You can assume the sequence will always contain valid directions (ie L, M, R) and that you will get a non-empty ternary tree.

string decodeSequence(TernaryTreeNode* tree, string sequence) {
    string message;

    for (char direction : sequence) {
        if (direction == 'L') {
            tree = tree->left;
        } else if (direction == 'M') {
            tree = tree->middle;
        } else {
            tree = tree->right;
        }

        if (!tree) {
            break;
        } 
        message += tree->ch;
    }
    return message;
}

2. Print All Paths (ternary.cpp)

We will use the same ternary definition above. Now, write a function

that prints all the valid paths to the leaves in the ternary tree. For example, in the ternary above, your function should print "LL", "LM", "LR", "MM", "RL", "RM", "RR". The order of your output doesn't matter.

void printAllPaths(TernaryTreeNode* tree, string soFar) {
    if (!tree) {
        return;
    }

    if (tree->isLeaf()) {
        cout << soFar << endl;
        return;
    }

    printAllPaths(tree->left, soFar + "L");
    printAllPaths(tree->middle, soFar + "M");
    printAllPaths(tree->right, soFar + "R");
}

void printAllPaths(TernaryTreeNode* tree) {
    printAllPaths(tree, "");
}

3. Palindromic Trees (palindromic.cpp)

A binary tree (not necessarily a binary search tree) is called a palindromic tree if it’s its own mirror image. For example, the tree on the left is a palindromic tree, but the tree on the right is not:

Write a function

that takes in a pointer to the root of a binary tree and returns whether it’s a palindrome tree.

// Wrapper function solution #1
bool isPalindromicTree(TreeNode* root) {
    return areMirrors(root, root);
}

// Wrapper function solution #2, more efficient
bool isPalindromicTree(TreeNode* root) {
    if (!root) {
        return true;
    }
    return areMirrors(root->left, root->right);
}

bool areMirrors(TreeNode* root1, TreeNode* root2) {
    /* If either tree is empty, both must be. */
    if (root1 == nullptr || root2 == nullptr) {
        return root1 == root2;
    }
 
    /* Neither tree is empty. The roots must have equal values. */
    if (root1->data != root2->data) {
        return false;
    }
 
    /* To see if they're mirrors, we need to check whether the left subtree of
    * the first tree mirrors the right subtree of the second tree and vice-versa.
    */
    return areMirrors(root1->left, root2->right) &&
           areMirrors(root1->right, root2->left);
}