12.1. Exercises

Many of these exercises are taken from past exams of ECE 244 Programming Fundamentals courses at University of Toronto. The solutions are provided in the answer boxes.

Headings in this page classify the exercises into different categories: [Easy], [Intermediate], and [Challenging]. I suggest you start by easy exercises and work your way up to the challenging ones.

Question 10 in Fall 2021 Final Exam [Easy]

Consider the following binary tree. The keys of the nodes are shown below inside the nodes.

1. What is the preorder traversal of the tree?

   Answer

   1 2 3 4 5 6 7

   (NLR) Nodes are visited recursively printing root node, left subtree then right subtree. This means when you print the left subtree, print it also by starting with the root, left node, then right node.

2. What is the inorder traversal of the tree?

   Answer

   3 2 4 1 5 7 6

   (LNR) Nodes are visited recursively printing left subtree, root node, then right subtree. This means when you print the left subtree, print it also by starting with the left node, root node, then right node.

3. What is the postorder traversal of the tree?

   Answer

   3 4 2 7 6 5 1

   (LRN) Nodes are visited recursively printing left subtree, right subtree, then root node. This means when you print the left subtree, print it also by starting with the left node, right node, then root node.

Question 9 in Fall 2022 Final Exam [Intermediate]

A binary tree is symmetric if the root node’s left subtree is exactly a mirror reflection of the right subtree. For example, the tree on the left is symmetric, but the tree on the right is not.

Fig. 12.1 This tree is symmetric

Fig. 12.2 This tree is not symmetric

Now, you are asked to complete the function is_symmetric. It should return true if and only if the root is a symmetric tree. You should fill out the recursive helper function is_symmetric_helper to make is_symmetric work as expected. Hint: you should write less than 15 lines of code.

/* Definition of the tree node */
class TreeNode {
 public:
  int data;
  TreeNode* left;
  TreeNode* right;
};

/* Recursive helper */
bool is_symmetric_helper(TreeNode* left, TreeNode* right);

bool is_symmetric(TreeNode* root) {
  if (root == NULL) {
    return true;
  }
  return is_symmetric_helper(root->left, root->right);
}

Complete the helper function is_symmetric_helper.

Answer

bool is_symmetric_helper(TreeNode* left, TreeNode* right) {
  if (left != NULL && right != NULL) {
    if (left->data == right->data) {
      return is_symmetric_helper(left->left, right->right) &&
             is_symmetric_helper(right->left, left->right);
    } else {
      return false;
    }
  } else {
    if (left == NULL && right == NULL) {
      return true;
    } else {
      return false;
    }
  }
}

In progress!