# Week 9 - Binary search trees
## Team
Team name: SampleText
Date: 4/20/1337
Members : Onurkan Kanli, Stephen van Rumpt, Hlib Hryshko
| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Hlib |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Onurkan |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Onurkan |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Stephen |
## Activities
### Activity 1: Maintaining order in Arrays and Linked Lists - reprise
| Algorithm | Array | Linked List |
| -------- | -------- | -------- |
| Value insertion | O(n) | O(n) |
| Value removal | O(n) | O(n) |
| Membership testing | O(log(n))| O(n) |
- Time complexity of value insertion:
For Array it will be O(n), because the program must find the place for it and move all the elements, which are bigger, one index to the right.
For Linked Linked it will be the same value of O(n), because the program must find the place for the element and just add new element.
- Time complexity of value removal:
For array it will be O(n), because the program firstly finds the value and then moves all the elements after it to the left. So it is just 1 for loop from 0 to n - 1, which equals to n.
For Linked List it will be O(n), because the program needs just to find the element and further it is just O(1) operation to insert a new element.
- Time complexity of membership testing
For Array the time complexity is O(log(n)), because binary search could be implemented and its time complexity is O(log(n)).
For Linked List the time complexity is O(n), because the program must check every element. There for it is one for loop from 0 to n - 1, which has time complexity of O(n).
### Activity 2: Recognizing BSTs
Out of these 3 trees, the Binary Search Tree is tree number 3.
- The first one is wrong, because the root value is bigger than a value in the right side of the tree(72 > 71)
- The second one is wrong, because a value in the right side is less then the parent value(84 < 85)
### Activity 3: Building a BST
The BST with 3 levels :
Code:
```c=
bintree_node root{5, new bintree_node
{3, new bintree_node
{2},
nullptr },
new bintree_node
{11, new bintree_node
{7},
nullptr}
};
```
Photo:
The BST with 4 levels:
Code:
```c=
bintree_node root{7,new bintree_node
{5, new bintree_node
{3, new bintree_node
{2},
nullptr},
nullptr},
new bintree_node
{11}
};
```
Photo:
The BST with 5 levels:
Code:
```c=
bintree_node root{11, new bintree_node
{7, new bintree_node
{5, new bintree_node
{3, new bintree_node
{2}, nullptr},
nullptr},
nullptr},
nullptr};
```
Photo:
### Activity 4: Searching for values
```c=
bintree_node *bintree_node::find(int value) {
if (m_value == value){
return this ;
} else if (m_value > value && left() != nullptr){
return left()->find(value) ;
} else if (m_value < value && right() != nullptr){
return right()->find(value) ;
} else {
return nullptr ;
}
}
```
### Activity 5: Inserting values
```c=
bintree_node* bintree_node::insert(int value) {
if (value > m_value){
if (m_right == nullptr){
m_right = new bintree_node(value, this);
return m_right;
} else {
return m_right->insert(value);
}
} else if(value < m_value){
if (m_left == nullptr){
m_left = new bintree_node(value, this);
return m_left;
} else {
return m_left->insert(value);
}
} else{
return nullptr;
}
}
```
Photo:
### Activity 6: Properties of the minimum value (Stephen)
- Can the minimum value in a node’s left subtree be greater than the minimum value in a node’s right subtree? Why (not)?
No because if the minimum value that we’re looking for is not contained in the root node, then it may be located either in the left or in the right subtree. To decide which of these two subtrees we must search, is determined by a simple comparison: if the value we’re looking for is smaller than the root value, we continue our search in the left subtree. The right subtree wil always have values greater than the left subtree.
- Can the node containing the minimum value have a left subtree? Why (not)?
No , The minimum value is the last left subtree because there is no value smaller than that one leftover.
- Which traversal strategy will lead to the node containing the minimum value of a tree?
If the minimum value that we’re looking for is not contained in the root node, Then its located in the left subtree. From there we can keep going left until there is no left subtree left.
### Activity 7: Finding the minimum value
And that's how you insert code blocks:
```c=
bintree_node &bintree_node::minimum() {
if (m_left == nullptr){
return *this;
} else{
return m_left->minimum();
}
}
```
### Activity 8: Removing leafs
```c=
if (m_left == nullptr && m_right == nullptr) {
m_parent->replace_child(this, nullptr);
return this;
}
```
Photo:
### Activity 9: Removing nodes that have one child
```c=
if (m_left == nullptr) {
m_parent->replace_child(this, m_right);
return this;
} else if (m_right == nullptr) {
m_parent->replace_child(this, m_left);
return this;
}
```
Photo:
### Activity 10: Moving values around
...
...
### Activity 11: Removing *full* nodes
```c=
auto removed = find(m_right->minimum().m_value);
m_value = removed->m_value;
return removed->remove();
```
Photo:
### Activity 12: Performance analysis
...
...
### Activity 13: Restoring balance (optional)
```c=
bintree_node *bintree_node::from_vector(const std::vector<int> &vector, int min_idx, int max_idx) {
int mid_idx = min_idx + (max_idx - min_idx)/2;
bintree_node * left{};
if (mid_idx - min_idx > 0){
left = from_vector(vector, min_idx, mid_idx);
}
bintree_node * right{};
if (max_idx - mid_idx > 1){
right = from_vector(vector, mid_idx + 1, max_idx);
}
return new bintree_node(vector[mid_idx], left, right);
}
```
Photo:
## Look back
### What we've learnt
This week we learnt about binray search trees and how to work with them.
### What were the surprises
The only real surprise we encountered was the dev bug with activity 9 but besides that no real problems arose. What may have been a surprise to some was how to work with a binary tree in the beginning.
### What problems we've encountered
As mentioned before, we only really got stuck at activity 9 with that bug, and some minor confusions surrounding activity 10 and 12.
### What was or still is unclear
Everything seems fairly clear to us. Binary trees in general were tricky at first but now seem a little bit like a breeze to work with.
### How did the group perform?
Everything seemed to be finished within 2 work days but those days were spread very far apart. Performance was questionable but in the end we managed to finish this week off pretty well.
Google Drive
Gist
Clipboard
Sign in with Wallet
