# Week 9 - Binary Trees
## Team
Team name:Error
Date:9/5/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. | Kaloyan Zhekov 511216 |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Hoang Minh Le 511907 |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Thanh Tran 516467 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Hoa Than 487272 |
## 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(N) |
| value removal | O(N) | O(N) |
| membership testing | O(N ) | O(N) |
### Activity 2: Constructing a binary tree
```c++
int main() {
bintree_node root{0}, left{-2}, right{2};
bintree_node right_left{1};
root.set_left(&left);
root.set_right(&right);
right.set_left(&right_left);
bintree_writer::write_dot("example.dot", root);
}
```
* 3 labels
```c++
digraph G {
node [shape = record,height=.1];
subgraph cluster1 {
label = ""
fontsize = 18
fontcolor = blue
a1 [label="<l> | {<c> 5} | <r> "]
a2 [label="<l> | {<c> 3} | <r> "]
a3 [label="<l> | {<c> 2} | <r> "]
a4 [label="<l> | {<c> 7} | <r> "]
a5 [label="<l> | {<c> 11} | <r> "]
a1:l -> a2:c
a2:l -> a3:c
a1:r -> a4:c
a4:r -> a5:c
}
}
```
* 4 labels
```c++
digraph G {
node [shape = record,height=.1];
subgraph cluster1 {
label = ""
fontsize = 18
fontcolor = blue
a1 [label="<l> | {<c> 3} | <r> "]
a2 [label="<l> | {<c> 2} | <r> "]
a3 [label="<l> | {<c> 5} | <r> "]
a4 [label="<l> | {<c> 7} | <r> "]
a5 [label="<l> | {<c> 11} | <r> "]
a1:l -> a2:c
a1:r -> a3:c
a3:r -> a4:c
a4:r -> a5:c
}
}
```
* 5 labels
```c++
digraph G {
node [shape = record,height=.1];
subgraph cluster1 {
label = ""
fontsize = 18
fontcolor = blue
a1 [label="<l> | {<c> 2} | <r> "]
a2 [label="<l> | {<c> 3} | <r> "]
a3 [label="<l> | {<c> 5} | <r> "]
a4 [label="<l> | {<c> 7} | <r> "]
a5 [label="<l> | {<c> 11} | <r> "]
a1:r -> a2:c
a2:r -> a3:c
a3:r -> a4:c
a4:r -> a5:c
}
}
```
### Activity 3: Recognizing BSTs
Record your answer here
Tree C is a binary search.
Tree A is not a binary search tree because not all the value on the right subtree are greater than the root’s value, in this case 71 is less than 72 and should be on the left hand side.
Tree B is not a binary search tree because not all the value in the root’s right subtree are greater than the root’s value, in this case 84 is less than 85 and should be on the left hand side of 85
### Activity 4: Searching for values
```c++
bintree_node *bintree_node::find(int value) {
(void) value;
std::vector<const bintree_node*>stack={this};
bintree_node* res= nullptr;
while(!stack.empty()){
auto node=stack.back();
stack.pop_back();
if(node->value()==value) {
res=const_cast<bintree_node*>(node);
}
if(node->left()!= nullptr)
stack.push_back(node->left());
if(node->right()!=nullptr)
stack.push_back(node->right());
}
return res;
}
```
### Activity 5: Inserting values
```c++
bintree_node* bintree_node::insert(int value) {
// Activity 5
// TODO: find the correct position to insert the node.
if (value == m_value)
return nullptr;
else if (value < m_value) {
if(has_left_child()){//check if left child node exist
return m_left->insert(value);
}
else{//if the left child node is not exist then create new left child node
bintree_node* temp=new bintree_node{value};
this->set_left(temp);
return this->m_left;
}
} else {
if(has_right_child()){//check if right child node exist
return m_right->insert(value);
}
else{//if the right child node is not exist then create new right child node
bintree_node* temp=new bintree_node{value};
this->set_right(temp);
return this->m_right;
}
}
}
```
### Activity 6: Properties of the minimum value
Record your answer here
Question 1: 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, it cannot. As the condition that the left child node is always smaller than parent node as well as smaller than right child node of parent node. Thus, even the greatest left child node will always smaller than the smallest right child node.
Question 2: Can the node containing the minimum value have a left subtree? Why (not)?
No, it cannot. If the node containing the minimum value has a left subtree, then it is not the node containing minimum value anymore, because the left child node of it is always containing the smaller value than its value.
Question 3: Which traversal strategy will lead to the node containing the minimum value of a tree?
Simple, we just travel in the left subtree until the left node has no left child.
### Activity 7: Finding the minimum value
```c++
bintree_node &bintree_node::minimum() {
bintree_node* current=this;
while(current->m_left!= nullptr){
current=current->m_left;
}
return *current;
}
```
### Activity 8: Removing leafs
```c++
if (is_leaf()) {
//Activity 8
if (m_parent->m_left != nullptr)
m_parent->replace_child(this, this->m_left);//we replace the child node of parent node
else if (m_parent->m_right != nullptr)
m_parent->replace_child(this, this->m_right);
return this;//always return to the node we want to delete
}
```
### Activity 9: Removing nodes that have one child
```c++
if (is_leaf()) {
//Activity 8
if (m_parent->m_left != nullptr)
m_parent->replace_child(this, this->m_left);//we replace the child node of parent node
else if (m_parent->m_right != nullptr)
m_parent->replace_child(this, this->m_right);
return this;//always return to the node we want to delete
} else if (has_right_child() && !has_left_child()) {
// Activity 9 - this node is a non-full node
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
m_parent->replace_child(this, this->m_left);
return this;
```
### Activity 10: Moving values around
Record your answer here
The left tree has values from A to G and, but it is missing a root. The left subtree begins with the value A while the right subtree begins with D. A has right child B and B has left child C, which means that in this BST the A is the smallest value, because B is on the right of A and so as is C. Thus the following inequality could be applied A<=C<=B. D is the smallest value from the right subtree. For this reason, we can put in the root B, because B>=A so A is kept in the left subtree and also C<=B. If we assume that F>=B then everything is fine and on the contrary comes the second option for out BST`s root. F could also be in the root, because E>=F and thus D. A is assumed to be smaller when is in the left subtree and also its child B.
The right tree would maintain the same principle. In simple words for the root the two most appropriate values should be the greatest value from the left subtree, because it will keep the smaller values on the left as they are now and the greater values on the right. The other appropriate is the smallest value from the right subtree that will keep track of the right values as they are greater and will be always on the right. The left values are assumed to be indeed smaller than the smallest in the right subtree. So for the right tree the best values are A<=C<=E<=G and E<=G<=H.
### 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 12: (Un)balanced trees
The three graphs all exhibit binary trees with varied related architectures. The root of the first network is 19 and it is connected to other nodes based on its value. The larger value is on the right node, forming the right subtree, while the lower value is on the left node, forming the left subtree. These nodes can include subtrees, but the insertion rule stays the same. The second is added with rising values, and everything is retained in the appropriate nodes. The third graph, with decreasing values, is placed and connected on the left side.
### Activity 13: Time complexity
| Operation | Time complexity (if balanced) | Time complexity (if unbalanced) |
| --------- | --------------- | --------------- |
| Lookup | O(H) | O(log(N)) |
| Insert | O(N) | O(log(N)) |
| Remove | O(H) | O(log(N)) |
## Looking back
### What we've learnt
Formulate at least one lesson learned.
Know about how binary search tree (BST) stores its data
Use recursion to implement insertion, removal, and membership testing
Implement search, insertion, and removal operations for a BST in C++.
### What were the surprises
nothing
### What problems we've encountered
nothing
### What was or still is unclear
nothing
### 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?
Perfect as usual
> Written with [StackEdit](https://stackedit.io/).
Sign in with Wallet
Connect another wallet