Lab #6: Trees

Due Date Wednesday, May 11th at 9pm.

The purpose of this lab is to give you practice working with:

  1. writing recursive functions,

  2. structures and pointers to structures, and

  3. navigating binary trees.

You’ll also get practice writing helper functions.

You must complete this lab on a CS Linux machine. You can use the machines in CSIL or can use VSCode + ssh on your own machine to get to one of the Linux servers.

Getting Started

You will be using the same repository for all the labs in this course. To pick up the files you need for this lab (aka, the distribution), you should navigate to your cmsc15200/labs-GITHUB_USERID directory (where GITHUB_USERID is replaced with your GitHub account name) and then run:

$ git pull upstream main

(We will use $ to indicate the Linux command-line prompt. It is not part of the command that you will run.)

If this command succeeded, you will have a subdirectory named lab6. You will do all of your work for this lab in this directory. See the file README.md for a description of the files in the distribution.

As in earlier labs, we have provided a Makefile that has targets for compiling your code with tests that you write, for compiling your code with our automated tests, and for cleaning up generated files.

Trees

In this lab, you will answer questions about binary trees. The tasks below make use of the following typedef and struct:

typedef struct inttree inttree_t;

struct inttree {
   int val;
   inttree_t *left
   inttree_t *right;
};

An inttree_t is one node in a tree with integer values. Each node stores an integer along with references to its left and right subtrees. left or right can be NULL if a node does not have a left or right subtree (or both, if it’s a leaf). As usual, the entire tree is represented using a pointer to the root node. You can find these definitions in lab6.h.

Restriction You do not need to make use of arrays anywhere on this lab. That is, you should not create an array representation of the nodes in a tree, then process that array. It is not necessary to use queues or other types of linked lists, either. All of the computations can be done using the tree directly.

None of the tasks require you to traverse the tree multiple times. That is, an efficient solution to each problem will involve visiting each tree node at most once. Make sure you are not making multiple passes over the tree.

We encourage you to use recursion throughout this assignment and to write helper functions where you see fit.

Deliverables

Task 1

Complete the function no_onlies which takes a pointer to an inttree_t and returns true if no node in the tree is an “only child” (“onlies” is a term for couples that have only one child). That is, this function returns true if no nodes in the tree have just one child, and false otherwise. This function should return true if the input tree is empty.

For example, consider the trees t1 and t2:

t1:              t2:
      5                5
     / \              / \
    3   7            3   7
   / \              /   / \
  1   4            1   8   9

  • A call to no_onlies with t1 should return true. Every node has either zero or two children.

  • A call to no_onlies with t2 should return false. The node with the value 3 has just one child. That is to say, the node with the value 1 is an only child.

Task 2

Complete the function postorder which takes a pointer to an inttree_t and num, an integer. postorder should search for num in t using postorder traversal and returns the number of steps it took to find num. If num is not in the tree, it should return the number of steps it took to determine that num is not in the tree.

Here are some examples:

  • A call to postorder with t1 and 7 should return 4. It takes 4 steps to find the value 7 in t1 using postorder traversal.

  • A call to postorder with t1 and 1 should return 1. It takes just 1 step to find the value 1 in t1.

  • A call to postorder with t1 and 8 should return 5. All 5 nodes in the tree need to be checked in order to determine that the value 8 is not in the tree.

  • A call to postorder with the empty tree (NULL) should return 0. There are no nodes to search in the empty tree.

A note about efficiency: This task can be completed with just one pass over the tree (or less, if val is found). That is, the number returned from postorder should really be the total number of nodes visited in order to find val. Make sure you’re not making multiple passes over the tree.

Hint: Consider using a helper function for this task. Remember that your helper functions should be properly documented.

Task 3

A path is a sequence of nodes in a tree that connects the root node to a leaf node.

Complete the function even_odd which takes a pointer to an inttree_t and returns true if every path in a tree from the root to a leaf alternates between even and odd numbers, and false otherwise. This function should return true if the input tree is empty (it is vacuously true).

Let t3 and t4 be the following trees:

t3:              t4:
    3                6
   / \              / \
  2   6            3   9
 /   / \          /   / \
1   5   9        2   5   8
       / \
      4   8

  • A call to even_odd with t3 should return true. Every path through t3 alternates between even and odd integers. Note that it doesn’t matter whether the path starts with an even or add number, as long as it alternates between the two.

  • A call to even_odd with t4 should return false. The path 6-9-5 does not alternate between even and odd integers.

Task 4

Complete the function path_adds_to which takes a pointer to an inttree_t and num, an integer, and returns true if there is a path of nodes in the tree whose values add to num, and false otherwise.

Here are some examples:

  • A call to path_adds_to with t3 and 14 should return true. The path 3-5-6 adds to 14.

  • A call to path_adds_to with t3 and 26 should return true. The path 3-6-9-8 adds to 26.

  • A call to paths_add_to with t3 and 10 should return false. There is no path in t3 that adds to 10.

  • A call to paths_add_to with the empty tree (NULL) and any number should return false. There are no paths in the empty tree that add to an integer.

Grading

Your grade on this assignment will be fully determined by the automated tests on Gradescope. There will not be a code quality portion of your grade for this lab.

If you do not implement code for a particular task, you will get a zero for that porition of the autograder. You will also recieve a zero for a task if you do not follow the restrictions stated above.

The weights for the tasks are:

  • Task 1: 20%

  • Task 2: 30%

  • Task 3: 25%

  • Task 4: 25%

Cleaning up

Before your submit your work, we strongly encourage you to get your directory into a clean state. Run make clean to remove any executables that are laying around and then run git status . to make sure you did not forget to add/commit any of the required files.

Also, remove directives, such as:

// YOUR CODE HERE

// Replace 0.0 with an appropriate return value

from your code. Make sure to recompile and rerun the tests after you clean up. It is easy to introduce a syntax error at this stage.

Submission

Before you upload your submission, make sure you have added the required information to the header comment in lab6.c:

  • your name,

  • the names of anyone beyond the course staff you discussed the assignment with, and

  • links to any resources that you used other than course materials and the course textbook.

Note: write None in the relevant field, to indicate that you did not use any sources and/or consult anyone beyond the course staff.

To submit your work, you will need to add, commit, and push lab6.c to GitHub and then upload your repository to Gradescope under the Lab #6 assignment.

You are welcome to upload your code to Gradescope multiple times before the deadline, but it is wildly inefficient to use Gradescope as a compute server. You should test your code on the CS Linux machines and only upload it when you think you are finished or when you are getting close to the deadline and want to do a “safety” submission.

You are responsible for making sure that the code you upload compiles and runs. You will get zero credit for code that does not compile.

Finally, a reminder that we will not accept late work.