EX15 - Recursive Structures

In Exercise 15, we will be constructing a recursive data structure based on what we learned in clas today (6/15). We will be defining a simple binary tree node, which is only a slight extension of our singly linked list node. The main difference is that instead of only having a single next attribute, TreeNode objects have a left and right attribute holding child trees.

0. Pull the skeleton code

You will find the starter files needed by “pulling” from the course workspace repository. Before beginning, be sure to:

  1. Be sure you are in your course workspace. Open the file explorer and you should see your work for the course. If you do not, open your course workspace through File > Open Recent.
  2. Open the Source Control View by clicking the 3-node (circles) graph (connected by lines) icon in your sidebar or opening the command palatte and searching for Source Control.
  3. Click the Ellipses in the Source Control pane and select “Pull” from the drop-down menu. This will begin the pulling process from the course repository. It should silently succeed.
  4. Return to the File Explorer pane and open the exercises directory. You should see it now contains the directory named ex15. If you expand those directories, you will see the starter files for this exercise.

If the above did not work, try the following:

  1. Click the Ellipses in the Source Control pane and select “Pull, Push” from the drop-down menu. Then select “Pull from”. Then select “upstream” and the main option. This will begin the pulling process from the course repository. It should silently succeed.
  2. Return to the File Explorer pane and open the exercises directory. You should see it now contains another directory named ex15. If you expand that directory, you should see the starter files

Part 1. Recursive Class Writing

Write a class called TreeNode with the following specifications:

  1. Each TreeNode object should have 3 attributes including:
    • an int attribute called data
    • an Optional[TreeNode] attribute called left
    • an Optional[TreeNode] attribute called right
  2. The TreeNode class should have a constructor that takes in data, left, and right, in this order. This means it will have 4 parameters including self.
    It should initalize all 3 attributes.

Part 2. Recursive Object Construction

We provide some starter code to help print out the binary trees for you. No worries about understanding this just yet – it is just meant to be a visual aid when constructing some example objects. We suggest playing around with this a bit to get comfortable with how a tree should look! Tree 0 is provided to you.

In main, construct three TreeNode objects with the following specifications:

Tree 0

  • Root node with data value 0
  • Left subtree is a single TreeNode with data value 1
  • Right subtree is a single TreeNode with data value 2
  • Produces the following output when printed:
    2
  0
    1

Tree 1

  • Root node with data value 0
  • Left subtree has data value 1 AND a left child that is a single TreeNode with a data value 2.
  • Right subtree is None
  • Produces the following output when printed:
    0
      1
        2

Tree 2

  • Root node with data value 0
  • Left subtree is a single TreeNode with data value 1
  • Right subtree has data value 2 AND left and right children that are both single TreeNodes with data values of ‘4’
  • Produces the following output when printed:
        4
      2
        4
    0
      1

2. Make a Backup Checkpoint “Commit”

As you make progress on this exercise, making backups is encouraged. Note that you do not have to make a backup in order to submit your work, though you are encouraged to before each submission so that you can revert back to a previous point in your project if you accidentally change something you did not intend to.

  1. Open the Source Control panel (Command Palette: “Show SCM” or click the icon with three circles and lines on the activity panel).
  2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
  3. Move your mouse’s cursor over the word Changes and notice the + symbol that appears. Click that plus symbol to add all changes to the next backup. You will now see the files listed under “Staged Changes”.
    • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
  4. In the Message box, give a brief description of what you’ve changed and are backing up. This will help you find a specific backup (called a “commit”) if needed. In this case a message such as, “Progress on Exercise 3” will suffice.
  5. Press the Check icon to make a Commit (a version) of your work.
  6. Finally, press the Ellipses icon (…), look for “Pull/Push” submenu, and select “Push to…”, and in the dropdown select your backup repository.

3. Submit to Gradescope for Grading

Login to Gradescope and select the assignment named “EX15 - Recursive Structures”. You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to Visual Studio Code.

If you do not see a Terminal at the bottom of your screen, open the Command Palette and search for “View: Toggle Integrated Terminal”.

To produce a zip file for ex15, type the following command (all on a single line):

python -m tools.submission exercises/ex15

In the file explorer pane, look to find the zip file named “21.mm.dd-hh.mm-exercises-ex15.zip”. The “mm”, “dd”, and so on, are timestamps with the current month, day, hour, minute. If you right click on this file and select “Reveal in File Explorer” on Windows or “Reveal in Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.

20 points of this assignment will be handgraded to check for proper construction of the objects!