# Week 9 - Binary Trees
## Team
Alexandra Melei
479787
Date: 18.05.2023
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |
## 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^2) | O(n) |
| value removal | O(n^2) | O(n) |
| membership testing | O(n) | O(n) |
### Activity 2: Constructing a binary tree
```c++
3 level bintree:
bintree_node root{2}, left{5}, right{3};
bintree_node right_left{7};
bintree_node right_right{11};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
right.set_right(&right_right);
bintree_writer::write_dot("example.dot", root);
4 level bintree:
bintree_node root{2}, left{5}, right{3};
bintree_node right_left{7};
bintree_node right_left_right{11};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
right_left.set_right(&right_left_right);
bintree_writer::write_dot("example.dot", root);
5 level bintree:
bintree_node root{2}, right{3};
bintree_node right_left{5};
bintree_node right_left_right{7};
bintree_node right_left_right_right{11};
root.set_right(&right);
right.set_left(&right_left);
right_left.set_right(&right_left_right);
right_left_right.set_right(&right_left_right_right);
bintree_writer::write_dot("example.dot", root);
```
### Activity 3: Recognizing BSTs
Record your answer here:
The 3rd one is a binary search tree, in the first there is a sub note on the right->left=71 and its supposed to be 72 or higher. On the second, root->right->right=84 and is smaller than 85 when it is on the right side and its supposed to be higher than 85.
### Activity 4: Searching for values
```c++
bintree_node * bintree_node::find(int value)
{
(void) value;
if(this == nullptr)
return nullptr;
else if(m_value==value)
return this;
else if(m_value > value)
return m_left->find(value);
else
return m_right->find(value);
}
```
### Activity 5: Inserting values
```c++
bintree_node* bintree_node::insert(int value) {
if (value == m_value)
return nullptr;
else if (value < m_value) {
if (this->has_left_child()) {
return m_left->insert(value);
} else {
m_left = new bintree_node{value, this};
return m_left;
}
}
else if (value > m_value) {
if (this->has_right_child()) {
return m_right->insert(value);
} else {
m_right = new bintree_node{value, this};
return m_right;
}
}
}
```
### Activity 6: Properties of the minimum value
The minimum value cannot be bigger in the left substree than in the right substree because to get into the right substree the value has to be bigger than the root while in the left substree it has to be smaller than the root.
The node containing the minimum value cannot have a left substree because it indicates that there are smaller values than itself, so it's not the minimum.
Strategy: keep to the left.
### Activity 7: Finding the minimum value
```c++
bintree_node &bintree_node::minimum() {
if(this->has_left_child())
{
return m_left->minimum();
}
else return *this;
}
```
### Activity 8: Removing leafs
```c++
bintree_node *bintree_node::remove() {
if (is_leaf()) {
this->m_parent->replace_child(this,nullptr);
return this;
} else if (!has_right_child()) {
// Activity 9 - this node only has a left child
} else if (!has_left_child()) {
// Activity 9 - this node only has a right child
} else {
// Activity 11 - this node is a full node
}
return nullptr;
}
```
### Activity 9: Removing nodes that have one child
```c++
bintree_node *bintree_node::remove() {
if (is_leaf()) {
this->m_parent->replace_child(this,nullptr);
return this;
} else if (!has_right_child()) {
this->m_parent->replace_child(this,this->m_left);
return this;
} else if (!has_left_child()) {
this->m_parent->replace_child(this,this->m_right);
return this;
} else {
// Activity 11 - this node is a full node
}
return nullptr;
}
```
### Activity 10: Moving values around
When we use an ordered binary tree it does not matter which substree we start moving up due to the fact that it is ordered. So if we want to remove the D node from
the first tree then we can move up lets say E. E<=G, E>=F will still hold as well as root<=E. This works even when we move up G. G>=E and root<=G.
If we take the second tree as an example and we remove A we can move up either B or C without any consequences. If we move up B then B<=C and B<=root will still be true. Or if we move up C then C>=B and C<=root will still hold up. Although in this case the child nodes have to be moved up the same way.
### Activity 11: Removing full nodes
```c++
bintree_node *bintree_node::remove() {
if (is_leaf())
{
this->m_parent->replace_child(this,nullptr);
return this;
}
else if (!has_right_child())
{
this->m_parent->replace_child(this,this->m_left);
return this;
}
else if (!has_left_child())
{
this->m_parent->replace_child(this,this->m_right);
return this;
}
else
{
auto &min = this->m_right->minimum();
this->m_value = min.m_value;
return min.remove();
}
return nullptr;
}
}
```
### Activity 12: (Un)balanced trees
Record your answer here
### 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) |
## Looking back
### What we've learnt
Formulate at least one lesson learned.
### What were the surprises
Fill in...
### What problems we've encountered
Fill in...
### What was or still is unclear
Fill in...
### How did the group perform?
How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?
Sign in with Wallet
Connect another wallet