Reading 02: Binary Trees

Readings

The readings for Monday, September 05 are:

1. Data Structures and Other Objects Using C++:

   • Chapter 10

2. The Biggest Changes in C++11 (and Why You Should Care)

3. Welcome Back to C++ (Modern C++)

   • Smart Pointers (Modern C++)

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

1. Data Structures & Algorithm Analysis

   • Chapter 5.1 - 5.3

2. Open Data Structures

   • Chapter 6.1

Questions

Once you have completed the readings, answer the following questions in the reading02/README.md file in your assignments repository:

1. Given a binary tree with N nodes.

   • What is the minimum height of the tree?

   • What is the maximum height of the tree?

   Answer in terms of Big-O.

2. Given the following binary tree:

   

   • How would you represent the binary tree using an array? Sketch the result using ASCII Art such as:

        0     1     2
     [ ... | ... | ... ]
     

   • When would it be better to use an array representation of a binary tree over the traditional node based representation?

3. Given the following binary tree:

   

   • Record the nodes you would visit if you performed a breadth-first traversal of the binary tree (assume you go left-to-right when crossing a layer).

     • What data structure would you use to perform this traversal and how would you use it?

   • Record the nodes you would visit if you performed a depth-first traversal of the binary tree (assume you are using a pre-order approach).

     • What data structure would you use to perform this traversal and how would you use it?

   Adaptor Container

   Answering with a generic container such as a linked list or array is not specific enough. Instead, you need to think about which sort of adaptor you would use.

4. Suppose we had the following struct Node:

   struct Node {
       int          value;
       struct Node *left;
       struct Node *right;
   };
   

   • Modify the struct Node above to use smart pointers.

   • What are the benefits of using smart pointers in this struct Node?

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 02 - TA assignment list.

$ cd path/to/repo                 # Go to your repository
$ git checkout master             # Make sure we are on master branch first
$ git pull                        # Make sure we have changes from GitLab
$ git checkout -b reading02       # Create reading02 branch
...                               # Do your work
$ git commit                      # Commit your work (can do this multiple times)
$ git push -u origin reading02    # Push branch to GitLab