# Week 9 - Binary Trees
## Team
Team name: Caca
Date: 04/05/2022
Members
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Taimour |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Hugo |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Iulian |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Arturo |
## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.
Download the provided project and open it in CLion.
### Activity 1: Maintaining order in arrays and linked lists - reprise
Record your answer here
| | Array | Linked List |
| ------------------ | ------ | ----------- |
| value insertion | O(n) | O(1) |
| value removal | O(n) | O(1) |
| membership testing | O(n) | O(n) |
### Activity 2: Constructing a binary tree
```c
//3 level tree
int main() {
bintree_node root{5}, left{3}, right{7};
bintree_node right_left{6};
bintree_node right_right{11};
bintree_node left_left{-1};
bintree_node left_right{2};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
right.set_right(&right_right);
left.set_left(&left_left);
left.set_right(&left_right);
bintree_writer::write_dot("example.dot", root);
}
//4 level tree
int main() {
bintree_node root{5}, left{3}, right{7};
bintree_node right_left{6};
bintree_node right_left_right{7};
bintree_node right_left_left{5};
bintree_node right_right{11};
bintree_node right_right_right{12};
bintree_node right_right_left{10};
bintree_node left_left{2};
bintree_node left_left_right{3};
bintree_node left_left_left{1};
bintree_node left_right{4};
bintree_node left_right_right{5};
bintree_node left_right_left{3};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
right.set_right(&right_right);
right_left.set_left(&right_left_left);
right_left.set_right(&right_left_right);
right_right.set_left(&right_right_left);
right_right.set_right(&right_right_right);
left.set_left(&left_left);
left.set_right(&left_right);
left_left.set_left(&left_left_left);
left_left.set_right(&left_left_right);
left_right.set_left(&left_right_left);
left_right.set_right(&left_right_right);
bintree_writer::write_dot("example.dot", root);
return 0;
}
//5 level tree
int main() {
bintree_node root{5}, left{3}, right{7};
bintree_node right_left{6};
bintree_node right_left_right{7};
bintree_node right_left_left{5};
bintree_node right_right{11};
bintree_node right_right_right{12};
bintree_node right_right_left{10};
bintree_node left_left{2};
bintree_node left_left_right{3};
bintree_node left_left_left{1};
bintree_node left_right{4};
bintree_node left_right_right{5};
bintree_node left_right_left{3};
bintree_node right_right_right_right{1};
bintree_node right_right_right_left{3};
bintree_node right_right_left_right{5};
bintree_node right_right_left_left{7};
bintree_node right_left_right_right{1};
bintree_node right_left_right_left{3};
bintree_node right_left_left_right{5};
bintree_node right_left_left_left{7};
bintree_node left_right_right_right{1};
bintree_node left_right_right_left{3};
bintree_node left_right_left_right{5};
bintree_node left_right_left_left{7};
bintree_node left_left_right_right{1};
bintree_node left_left_right_left{3};
bintree_node left_left_left_right{5};
bintree_node left_left_left_left{7};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
right.set_right(&right_right);
right_left.set_left(&right_left_left);
right_left.set_right(&right_left_right);
right_right.set_left(&right_right_left);
right_right.set_right(&right_right_right);
left.set_left(&left_left);
left.set_right(&left_right);
left_left.set_left(&left_left_left);
left_left.set_right(&left_left_right);
left_right.set_left(&left_right_left);
left_right.set_right(&left_right_right);
right_right_right.set_right(&right_right_right_right);
right_right_right.set_left( &right_right_right_left);
right_right_left.set_right( &right_right_left_right);
right_right_left.set_left( &right_right_left_left);
right_left_right.set_right( &right_left_right_right);
right_left_right.set_left( &right_left_right_left);
right_left_left.set_right( &right_left_left_right);
right_left_left.set_left( &right_left_left_left);
left_right_right.set_right( &left_right_right_right);
left_right_right.set_left( &left_right_right_left);
left_right_left.set_right( &left_right_left_right);
left_right_left.set_left( &left_right_left_left);
left_left_right.set_right( &left_left_right_right);
left_left_right.set_left( &left_left_right_left);
left_left_left.set_right( &left_left_left_right);
left_left_left.set_left( &left_left_left_left);
bintree_writer::write_dot("example.dot", root);
return 0;
}
```
### Activity 3: Recognizing BSTs
Record your answer here
Tree C is a binary search tree as it adheres to the rules, each left node is lower than it's parent, each right node is higher than it's right parent and all nodes only have 2 children.
Tree B is wrong since it has a right node value higher than it's parent value.
### Activity 4: Searching for values
```c
bintree_node *bintree_node::find(int value) {
// Activity 4
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node == nullptr) {
return nullptr;
} else if (current_node->m_value > value) {
current_node = current_node->m_left;
} else if (current_node->m_value < value) {
current_node = current_node->m_right;
} else {
return current_node;
}
}
return nullptr;
}
```
### Activity 5: Inserting values
```c
bintree_node* bintree_node::insert(int value) {
// Activity 5
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (value == m_value) {
return nullptr;
} else if (current_node->m_value > value) {
if (current_node->m_left == nullptr) {
current_node->m_left = new bintree_node{value};
current_node->m_left->m_parent = this;
return current_node->m_left;
} else {
current_node = current_node->m_left;
}
} else {
if (current_node->m_right == nullptr) {
current_node->m_right = new bintree_node{value};
current_node->m_right->m_parent = this;
return current_node->m_right;
} else {
current_node = current_node->m_right;
}
}
}
return nullptr;
}
```
### Activity 6: Properties of the minimum value
Question 1: It can't because a value lower than the one in the left most tree can never go in the right because it would be also lower than the root node.
Question 2: Yes, because there can be a new value even lower than the minimum.
Question 3: Going left every single node until the next node is null, since every value that is lower than the previous will always go left.
### Activity 7: Finding the minimum value
```c
bintree_node &bintree_node::minimum() {
// Activity 7
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node->m_left == nullptr) {
return *current_node;
} else {
current_node = current_node->m_left;
}
}
return *this;
}
```
### Activity 8: Removing leafs
```c
bintree_node *bintree_node::remove() {
if (is_leaf()) {
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, nullptr);
}
return this;
} else if (has_right_child()) {
} else if (has_left_child()) {
} else {
}
}
```
### Activity 9: Removing nodes that have one child
```c
bintree_node *bintree_node::remove() {
if (is_leaf()) {
// Activity 8
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, nullptr);
}
return this;
} else if (has_right_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_right);
}
return this;
} else if (has_left_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_left);
}
return this;
} else {
}
}
```
### Activity 10: Moving values around
Record your answer here:
The way to move a branch as a new root is quite simple, we can just take minimum value of the right branch.
This ensure that the new head of the tree will be always smaller than every value in the right branch, but at the same time larger that every value of the left branch. Picture as example below.
### Activity 11: Removing full nodes
There is a function before_minimum() similar(recycled) to minimum() that i have used, see at the bottom.
```c
bintree_node *bintree_node::remove() {
if (is_leaf()) {
// Activity 8
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, nullptr);
}
return this;
} else if (has_right_child() && !has_left_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_right);
}
return this;
} else if (has_left_child() && !has_right_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_left);
}
return this;
} else {
// Activity 11 - this node is a full node
if (this->parent() != nullptr) {
this->m_value = this->m_right->minimum().m_value;
if (!this->m_right->has_right_child() && !this->m_left->has_left_child()) {
this->m_right = nullptr;
} else {
this->m_right->before_minimum().m_left = nullptr;
}
return new bintree_node{5};
}
}
return nullptr;
}
bintree_node &bintree_node::before_minimum() {
// Activity 7
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node->m_left->m_left == nullptr) {
return *current_node;
} else {
current_node = current_node->m_left;
}
}
return *this;
}
```
### Activity 12: (Un)balanced trees
The values inserted in a binary search tree are not really important, but the order they are inserted very much is.
If we insert the values at random, we will get a normal tree, but if we put them in descending order the values will always be on the left branch of each value and the opposite for ascending order.
In case of a sorted list inserted into a tree, the tree will act very similar to a linked list, with the difference that the way the values are ordered in can be on the left or right.
### Activity 13: Time complexity
| Operation | Time complexity (if balanced) | Time complexity (if unbalanced) |
| --------- | --------------- | --------------- |
| Lookup | O(log(n)) | O(n) |
| Insert | O(log(n)) | O(n) |
| Remove | O(log(n)) | O(n) |
**Full bintree_node.cpp file**
```c
//
// Created by Saxion on 4/10/2021.
//
#include "bintree_node.h"
bintree_node::bintree_node(int value, bintree_node *parent) :
m_value{value}, m_left{}, m_right{}, m_parent{parent} {
}
int bintree_node::value() const {
return m_value;
}
const bintree_node *bintree_node::left() const {
return m_left;
}
const bintree_node *bintree_node::right() const {
return m_right;
}
const bintree_node *bintree_node::parent() const {
return m_parent;
}
bool bintree_node::is_leaf() const {
return m_left == nullptr && m_right == nullptr;
}
bool bintree_node::has_left_child() const {
return m_left != nullptr;
}
bool bintree_node::has_right_child() const {
return m_right != nullptr;
}
/// Searches the subtree rooted at this node for the given value,
/// exploiting the fact that data is sorted.
/// \param value the value searched for
/// \return the node that contains the value, or nullptr if no node was found
bintree_node *bintree_node::find(int value) {
// Activity 4
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node == nullptr) {
return nullptr;
} else if (current_node->m_value > value) {
current_node = current_node->m_left;
} else if (current_node->m_value < value) {
current_node = current_node->m_right;
} else {
return current_node;
}
}
return nullptr;
}
/// Inserts the given value into the tree if the value is not yet present. Makes sure that the order invariant
/// is kept intact.
/// \param value the value to be inserted
/// \return a pointer to the node that was added, or nullptr if no node was added
bintree_node* bintree_node::insert(int value) {
// Activity 5
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (value == m_value) {
return nullptr;
} else if (current_node->m_value > value) {
if (current_node->m_left == nullptr) {
current_node->m_left = new bintree_node{value};
current_node->m_left->m_parent = this;
return current_node->m_left;
} else {
current_node = current_node->m_left;
}
} else {
if (current_node->m_right == nullptr) {
current_node->m_right = new bintree_node{value};
current_node->m_right->m_parent = this;
return current_node->m_right;
} else {
current_node = current_node->m_right;
}
}
}
return nullptr;
}
/// Removes the value contained in this node from the tree. This means that either this
/// node or another node (in case this node is a full node) is removed
/// \return
bintree_node *bintree_node::remove() {
if (is_leaf()) {
// Activity 8
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, nullptr);
}
return this;
} else if (has_right_child() && !has_left_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_right);
}
return this;
} else if (has_left_child() && !has_right_child()) {
// Activity 9 - this node is a non-full node
if (this->parent() != nullptr) {
this->m_parent->replace_child(this, this->m_left);
}
return this;
} else {
// Activity 11 - this node is a full node
if (this->parent() != nullptr) {
this->m_value = this->m_right->minimum().m_value;
if (!this->m_right->has_right_child() && !this->m_left->has_left_child()) {
this->m_right = nullptr;
} else {
this->m_right->before_minimum().m_left = nullptr;
}
return new bintree_node{5};
}
}
return nullptr;
}
void bintree_node::set_left(bintree_node *new_left) {
m_left = new_left;
if (m_left != nullptr)
m_left->m_parent = this;
}
void bintree_node::set_right(bintree_node *new_right) {
m_right = new_right;
if (m_right != nullptr)
m_right->m_parent = this;
}
void bintree_node::replace_child(const bintree_node *child, bintree_node *new_child) {
if (child == nullptr) {
throw std::invalid_argument(
"can't replace non-existing (nullptr) child of node[" + std::to_string(m_value) + "]");
} else if (m_left == child)
set_left(new_child);
else if (m_right == child)
set_right(new_child);
else
throw std::invalid_argument(
"node[" + std::to_string(child->m_value) + "] is not a child of node[" + std::to_string(m_value) + "]");
}
/// Returns a reference to the node containing the smallest value of the subtree rooted at this node
/// \return a reference to the node containing the minimum value
bintree_node &bintree_node::minimum() {
// Activity 7
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node->m_left == nullptr) {
return *current_node;
} else {
current_node = current_node->m_left;
}
}
return *this;
}
bintree_node &bintree_node::before_minimum() {
// Activity 7
bintree_node *current_node = this;
bool loop = true;
while(loop) {
if (current_node->m_left->m_left == nullptr) {
return *current_node;
} else {
current_node = current_node->m_left;
}
}
return *this;
}
```
## Looking back
### What we've learnt
How to work with BST and the logic behind them. Garnered a better grasp of working with pointers.
### What were the surprises
The similarity to a linked list.
### What problems we've encountered
None
### What was or still is unclear
Nothing, we have a good grasp of how trees function.
### How did the group perform?
This week we worked during spring vacation so we were a little slow.
> Written with [StackEdit](https://stackedit.io/).
Google Drive
Gist
Clipboard
Sign in with Wallet
