# Week 9 - Binary Trees
## Team
Team name: Totally Useless Inc.
Date: 2022/05/18
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. | Ines |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Tautvydas |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Adelina |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Stefan |
## Activities
### Activity 1: Maintaining order in arrays and linked lists - reprise
| | Array | Linked List |
| ------------------ | ------ | ----------- |
| value insertion | O(n) | O(n^2) |
| value removal | O(n) | O(1) |
| membership testing | O(log(n)) | O(n) |
### Activity 2: Constructing a binary tree
#### With Three Levels:
```c
int main() {
bintree_node root{2}, left{3}, right{5};
bintree_node right_right{11};
bintree_node right_left{7};
root.set_left(&left);
root.set_right(&right);
right.set_right(&right_right);
left.set_right(&right_left);
bintree_writer::write_dot("example.dot", root);
}
```
#### With Four Levels
```c
int main() {
bintree_node root{2}, left{3}, right{5};
bintree_node left_left{7};
bintree_node left_left_left{11};
root.set_left(&left);
root.set_right(&right);
left.set_left(&left_left);
left_left.set_left(&left_left_left);
bintree_writer::write_dot("example.dot", root);
}
```
#### With Five Levels
```c
int main() {
bintree_node root{2}, right{3};
bintree_node right_right{5};
bintree_node right_right_left{7};
bintree_node right_right_left_right{11};
root.set_left(&right);
right.set_right(&right_right);
right_right.set_left(&right_right_left);
right_right_left.set_right(&right_right_left_right);
bintree_writer::write_dot("example.dot", root);
}
```
### Activity 3: Recognizing BSTs
The Tree C is the only one that is a BST just because it is the only one that follows all the order invariant rules. The Tree A is not a BST because 71 is on the right side but it is not bigger than or equal to the root node and finally, The Tree B is not a BST because of 84 that integer is on the right so it should have been greater than 85.
### Activity 4: Searching for values
```c
bintree_node * bintree_node::find(int value) {
bintree_node* search =this;
while(search->has_left_child() || search->has_right_child() || search->m_value==value) {
if (search->m_value == value) {
return search;
} else {
if (search->m_value < value && search->has_right_child()) {
search = search->m_right;
} else if (search->m_value > value && search->has_left_child()) {
search = search->m_left;
}
else return nullptr;
}
}
return nullptr;
}
```
### Activity 5: Inserting values
```c
bintree_node* bintree_node::insert(int value) {
if (value == m_value)
return nullptr;
else if (value < m_value) {
if (has_left_child()){
return m_left->insert(value);
}else {
m_left = new bintree_node{value, this};
return m_left;
}
} else {
if (has_right_child()){
return m_right->insert(value);
}
else {
m_right = new bintree_node{value, this};
return m_right;
}
}
return nullptr;
}
```
### Activity 6: Properties of the minimum value
#### Questions:
* Can the minimum value in a node’s left subtree be greater than the minimum value in a node’s right subtree? Why (not)?
* Can the node containing the minimum value have a left subtree? Why (not)?
* Which traversal strategy will lead to the node containing the minimum value of a tree?
#### Answers:
* The minimum value in a node's left subtree **cannot** be greater than the minimum value in a node's right subtree. This is because the minimum value in a node's left subtree will be less than the binary tree's root, whereas the any value, including the minimum value, in a node's right subtree will be greater than the binary tree's root.
* The minimum value will always be the leftmost node, therefore it cannot have a left subtree.
* Recursively traversing from the root node the left child node until a NULL is returned. The node whose left node is pointing to NULL will be the minimum value in of the tree.
### Activity 7: Finding the minimum value
```c
bintree_node &bintree_node::minimum() {
if(this->has_left_child()){
bintree_node* currentNode = this->m_left;
while(currentNode->has_left_child()){
currentNode = currentNode->m_left;
}
return *currentNode;
}
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()) {
} else if (has_right_child()) {
this->m_parent->replace_child(this, this->m_left);
} else if (has_left_child()) {
this->m_parent->replace_child(this, this->m_right);
} else {
}
}
```
### Activity 10: Moving values around
For the first tree the nodes are: B and F because we are looking for the rightmost node of the left subtree or the leftmost of the right subtree. The B and F nodes check due to the fact that: A <= B <= C and D > B. F checks because D > F and F => A. For the second tree the same reasoning applies. The nodes that qualify are E and G - A <= E < F and A <= G < F
### Activity 11: Removing full nodes
```c
bintree_node *bintree_node::remove() {
if (is_leaf()) {
} else if (has_right_child()) {
} else if (has_left_child()) {
} else
{
// Activity 11
bintree_node *temp = &m_right->minimum();
this->m_value=temp->value();
temp->m_parent->replace_child(temp,temp->m_left);
return temp;
}
}
```
### Activity 12: (Un)balanced trees
Tree one:
Tree two:
Tree three:
* The difference between the three trees is that the first tree is balanced while the two other trees are unbalanced.
* The values in the first tree were arbitrary which makes the values go on the right and left side.
* In the second tree the values were increasing so all the values were going to the right side of the previous value.
* For the third tree the values are decreasing which makes them all go to the left side of the previous value.
### Activity 13: complexity
| Operation | Time complexity (if balanced) | Time complexity (if unbalanced) |
| --------- | --------------- | --------------- |
| Lookup | O(log2n) or O(height) | O(n) |
| Insert | O(log2n) or O(height) | O(n) |
| Remove | O(log2n) or O(height) | O(n) |
## Looking back
### What we've learnt
We learned about what binary trees are, how to perform operations on them and the time complexities
### What were the surprises
There were no surprises.
### What problems we've encountered
We had problems with vizualizing the binary tree when it was too long so we needed to resort to papers.
### What was or still is unclear
Everything was pretty clear and relatively easy to understand.
### How did the group perform?
The group performed well this week we managed to split the tasks and also effectively collaborate on finishing up the tasks.
Sign in with Wallet
Connect another wallet