You can compile your code using the provided Makefile via the make command

Learning Goal: I’m working on a c++ question and need guidance to help me learn.

Upon Passing my task i’ll tip in $100.

We then introduced the AVL Tree, which is another self-balancing BST but with strict bounds on the “balance factor” (right height minus left height) of every node.

Task: Edit BinaryTree.cpp

In this part of the assignment, we have provided a file called BinaryTree.cpp that contains a basic implementation of a binary tree. Function headers (with usage details) are included in BinaryTree.h, and you need to fill in the balanceFactors() function of the BinaryTree class. Be sure to only modify BinaryTree.cpp: do not modify BinaryTree.h.

We will not be checking for memory leaks, as we will be creating the dynamic objects, not you. We have provided a tester program, BinaryTreeTest, that will help you test your BinaryTree class.

Compiling and Running

You can compile your code using the provided Makefile via the make command:

$ make g++ -Wall -pedantic -g -O0 -std=c++11 -o BinaryTreeTest BinaryTreeTest.cpp BinaryTree.cpp

If you want to clean up your environment by deleting all the compiled executables, you can simply run make clean:

$ make clean rm -f BinaryTreeTest *.o

When run from the command line, BinaryTreeTest will print every node’s balance factor to standard output, and it will print the tree (in the Newick format) to standard error. You can run the tester program and direct the balance factors to a file called balance_factors.tsv and the tree to a file called tree.nwk as follows (the > operator redirects standard output to a file, and the 2> operator redirects standard error to a file):

$ ./BinaryTreeTest > balance_factors.tsv 2> tree.nwk

You can then open balance_factors.tsv in any text editor or spreadsheet viewer, and you can open tree.nwkin a tree-viewing tool like IcyTree. To use IcyTree, you can do the following:

1. Load the tree (File → Load from file… → select your tree file)
2. By default, IcyTree ladderizes the tree, which we don’t want because we need to check balance factors, so “left” and “right” have meaning in our context. We need to disable this feature (Style → Node sorting → Unsorted)
3. By default, IcyTree only displays leaf labels, so we need to show internal nodes as well (Style → Internal node text →Label)

The grader depends on this standard output, so be sure to remove any print statements from your code before you submit, otherwise the grader will mark your code as incorrect!

Optional Challenges

After you have successfully completed the above task and have already submitted and graded your code, here are some optional challenges you can try out:

Speed Up via Memoization

As you likely noticed while working on a solution to this computational problem, in order to compute the balance factor of a given node u, you need to first compute the heights of the left and right children of u. A naive solution could recursively compute the heights of the two children of u and then use those heights to compute the balance factor of u. However, because the heights of the descendants are not stored anywhere, this approach will result in wasted compute time caused by having to repeatedly recompute the heights of the nodes in the tree.

Instead, you could take advantage of memoization: storing the intermediate results for O(1) lookup in the future. Specifically, as you compute the heights of various nodes in the tree, instead of simply returning the height of the current node u, you can first store its height in a data structure (e.g. an unordered_map), and next time you attempt to find the height of node u, you can simply look up and return the value you already stored when you first computed it.

Simplify Code via Lambda Expressions

Computing the balance factors of the nodes in a binary tree requires us to compute the heights of the nodes in a binary tree, and a common approach for implementing both of these tasks is to define helper functions (e.g. one helper function to recursively compute the heights of the nodes in the tree, and perhaps a second helper function to recursively compute the balance factors of the nodes in the tree).

However, in principle, these two tasks are really sub-tasks of the BinaryTree::balanceFactors() function, and as such, it would be nice if the logic for implementing these sub-tasks could be nested within the BinaryTree::balanceFactors() function implementation. Is it possible to somehow write a function within a function? In C++11 and later, you can use a lambda expression to achieve precisely this functionality!