This class is about binary trees implementation. It is therefore convenient that you know what was discussed on the lectures:
The exercises for this class will involve the low level implementation
of binary trees and adding new methods, so that you can gain a better understanding of trees and how they work, while at the same time training your algorithmic abilities.
On the following classes you will be allowed to use any STL classes that use trees as the underlying implementation (such as sets or maps), but for this class we want you to be able to understand (and code) an implementation. Moreover, unlike lists, C++ does not provide a native binary tree class ready to be used.
This class includes the following implementation exercises available on Mooshak:
1. Understanding Binary Trees
(the goal of this exercise is for you to understand what a binary tree is and some of the orders in which we could traverse its nodes)
One way of describing a tree is to use one of the following representations:
Consider for instance the tree of the following figure:
Using the 4 representations given before, the tree would be described as:
To make sure you understood, write down the four representations given (preorder, inorder, postorder, breadth-first) but for the following tree:
- preorder: 6 8 4 3 5 1 7
- inorder: 8 4 6 1 5 3 7
- postorder: 4 8 1 5 7 3 6
- breadth-first: 6 8 3 4 5 7 1
2. A binary tree implementation
(the goal of this exercise is for you to understand a basic implementation of binary trees that uses templates)
Start by downloading the following two files: binaryTree.h (see it in html) and testBTrees.cpp (see it in html). This is the same BTree<T> class that was shown in the lectures.
Compile the code. The whole BTree<T> class is contained in the .h file, so you just need to compile testBTrees.cpp (make sure they are in the same directory, so that the line #include "binaryTree.h" knows where to find the file it wants to include). If you are on a shell, you could for instance run g++ -std=c++17 -Wall -o testBTrees testBTrees.cpp to obtain an executable with the name testBTrees.
Download the file input.txt containing a line with 5 1 8 N N 6 N N 7 2 N N N. This is the serialization of the tree in the following figure: its preorder representation with N explicitly representing the nullptr nodes (as seen in the lectures, this is enough to rebuild the tree, while the preorder alone is not):
(the two representations in this figure refer to the same tree)
Now run the test code you compiled giving as input the file you downloaded (equivalent to writing its contents as the input):
./testBTrees < input.txt
You should obtain the following as the output:
numberNodes = 6 height = 2 contains(2) = 1 contains(3) = 0 PreOrder: 5 1 8 6 7 2 InOrder: 8 1 6 5 2 7 PostOrder: 8 6 1 2 7 5 BFS: 5 1 7 8 6 2 DFS: 5 1 8 6 7 2
Notice that the PreOrder and DFS lines are equal, and this is not a mistake: the DFS with a stack (printDFS()) visits the nodes in the same order as the recursive PreOrder (see slides 28 and 29).
Have a look at each method being called in binaryTree.h to understand how the binary tree is implemented. The figure above gives you an overview of how the class is organized, and the comments in the code point to the slides where each method was explained in the lectures.
Notice how the implementation uses templates to be general and therefore supports any data type (not just int).
To make sure you understand how to use it, create a file input2.txt that gives the serialization of the following tree, ready to be read by the class, and give it as input to your program, testing if it gives the correct output.
The file input2.txt should contain: apple orange apricot N N kiwi melon N N N cherry N pear banana N N grape N N
You can read this tree with the code:
BTree<std::string> t;
t.read("N");
If you are reusing the testBTrees.cpp file, notice that lines such as t.contains(2) will now give an error, because they should have a string as an argument (e.g. t.contains("orange")).
Before you start: adding methods to the class
In exercises 3 to 9 you will be adding methods to the BTree<T> class (only the challenge is different). Add the requested method at the end of the class (but before the closing bracket), together with any recursive helper it needs, just like numberNodes() and its helper. You only need to submit the binaryTree.h file!
If you want to test the method on your computer, you can copy the tester code from the problem statement (use the Copy button above it) to a file on your computer, compile it and use the example input to see if the results are as expected (note how easy it is to add new inputs, if you want to make further tests - you can simply give new trees with their serialization, as shown in exercise 2).
If your program crashes with Segmentation fault (often a missing nullptr check in a recursive method), compile it again with g++ -std=c++17 -Wall -g -fsanitize=address ... and run it: the error message will then show the method and the line where the crash happened. (This works on Linux and macOS; it is not available with MinGW on Windows.)
Two things to keep in mind:
3. Your first binary tree method
For this exercise you will be solving the problem [AED039] Counting Leaves.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
This problem asks you to traverse the tree and count all leaves. Have a look at numberNodes(). What do you need to change to implement the numberLeaves method?
- The number of leaves in a tree is equal to the number of leaves in the left subtree plus the number of leaves in the right subtree
- A base case is when the current node is a leaf... in which case we should return 1
- Another base case is when the current node is nullptr... in which case we should return 0
4. A boolean tree method
For this exercise you will be solving the problem [AED040] Strictly Binary Trees.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- A tree is strictly binary if BOTH its subtrees (left and right) are strictly binary.
- At each node, you must check if it is valid, i.e. if it is a leaf or if it has two children:
. If it's not valid, just return... false!
. If it is valid, you still need to check that BOTH the left and right subtrees are also strictly binary.
5. Processing Paths
For this exercise you will be solving the problem [AED041] Tree Paths.
Desired time complexity: \(\mathcal{O}(|s|)\) (where |s| is the length of the path, which is at most the height of the tree: you only need to visit the nodes on the path, not the whole tree)
Notice that the method returns a reference (T &) to the value stored in the node. This means it can also be used to change the tree: in the example of the problem statement, t.path("LR") = 42; replaces the value 5 by 42. This is why path is not declared const, unlike the other methods you write this week: it gives access that allows changing the tree.
- You do not even need recursion: start with a pointer to the root and, for each character of s, move to the left or to the right child. At the end, return the value of the node you reached
- If you prefer recursion, besides the current node your helper method could have as arguments the path string s and the integer position pos where you are in the path. Looking at s[pos] you decide if you go to the left or to the right, calling the same method for that child... but with the position incremented!
- In both cases, do not forget the special path "_", which represents the root
6. Number of nodes at a certain depth
For this exercise you will be solving the problem [AED042] Deep Nodes.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- Can you do one exercise without any hints? 😉
7. Counting Even Nodes
For this exercise you will be solving the problem [AED043] Even Nodes.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- This problem is similar to counting the nodes or counting the leaves
- Instead of counting everything or just the leaves, count only the ones which are even (use the % operator to check for the remainder when divided by 2)
8. Sum of the nodes at a certain depth level
For this exercise you will be solving the problem [AED044] Sum of All Levels.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- Start by creating a vector with size equal to the height + 1 (note you already have a method for computing the height)
- While you are traversing the tree, if you keep track of which depth level you are at, you can just add to the corresponding position in the vector (assuming you are also passing around a reference to the vector)
9. The path of maximum sum
For this exercise you will be solving the problem [AED045] Maximum Sum Path.
Desired time complexity: \(\mathcal{O}(N)\) (where N is the number of nodes in the tree)
- One more without hints? 😉
The main idea of the challenge problems is to give you the opportunity of improving your problem solving abilities.
For this exercise you will be solving the problem [AED046] Recovering Lost Trees.
For this class, the problem is easier than the last one, but involves... trees! (of course 😁)
The input limits are small, so it is "just" about correctness.
Since this is a challenge, I will not give you any hints, but if you are stuck just contact @PedroRibeiro on Discord. Feel free to also contact @PedroRibeiro to discuss your accepted solution.
Happy coding! 😊