---
# System prepended metadata

title: Untitled

---

] # Week 9 - Binary search trees

## Team

Team name: Group 7
Date: 2021-04-28

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.                                             | Job Meulenbeld  |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              | Len Bauer |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |  Elitsa Marinova    |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |   Mihhail Tsulinda   |

## Activities

### Activity 1: Maintaining order in Arrays and Linked Lists - reprise

|   	            |   Array	|   Linked List	|
|---	    |---	    |---	    |
|   value insertion	|   O(n)	|   O(n)	|
|   value removal	|   O(n)	|   O(n)	|
|   membership testing	|   O(1)	|   O(n)	|

### Activity 2: Recognizing BSTs

BST is tree C.</br> 
Tree A breaks at leaf 71, which is to the right of the root 72.</br>
Tree B breaks at leaf 84, which is to the right of the parent 85.

### Activity 3: Building a BST

![5 levels](https://i.ibb.co/tKyDzmN/graphviz.png)
![3 levels](https://i.ibb.co/MkXSBBx/graphviz1.png)
![4 levels](https://i.ibb.co/dJwGZnd/graphviz2.png)

### Activity 4: Searching for values

```c
bintree_node *bintree_node::find(int value) {
    
	if(this != nullptr){
		if( this->m_value == value ){
			return this;
		}
		if( this->m_value > value ){
			return this->m_left->find(value);
		}
		if( this->m_value < value ){
			return this->m_right->find(value);
		}
	}
    return nullptr;
}
```

### Activity 5: Inserting values

```c
bintree_node* bintree_node::insert(int value) {

    if(this->m_value > value)
        {
            if(this->m_left == nullptr)
        {
            	this->m_left = new bintree_node{value};
            	m_left->m_parent = this;
            	return this->m_left;
        }
            return m_left->insert(value);
        }
    if(this->m_value < value)
    {
    	if(this->m_right == nullptr)
    	{
    		this->m_right = new bintree_node{value};
    		m_right->m_parent = this;
    		return this->m_right;
    	}
    	return m_right->insert(value);
    }

    return nullptr;
}
```

### Activity 6: Properties of the minimum value

* It could not. If the minimum from the left branch would be greater it would be sorted to the right branch.
* It could not. The minimum will always take the left-most position it the tree.
* Always go left.

### Activity 7: Finding the minimum value

And that's how you insert code blocks:

```c
bintree_node &bintree_node::minimum() {
    bintree_node *node = this;
    while(node->m_left != nullptr)
	{
    	node = node->m_left;
	}

    return *node;
}
```

### Activity 8,9 and 11:

```c
bintree_node *bintree_node::remove() { // TODO: Blue pill or red pill, memory leak or sigfault, choose wisely Neo.

	auto node = this;

    if (m_left == nullptr && m_right == nullptr) {
        m_parent->replace_child(this, nullptr);
		return node;
    } else if (m_left == nullptr) {
		m_parent->replace_child(this, m_right);
		return node;
    } else if (m_right == nullptr) {
        m_parent->replace_child(this, m_left);
		return node;
    } else {
        bintree_node &M = this->m_right->minimum();
        m_value = M.m_value;
        M.remove();
        return &M;
    }
}
```

###Activity 10:

Left tree: F and G (if D = G)
Right tree: E and J

### Activity 11: Removing *full* nodes

### Activity 12: Performance analysis

* ```O(n)``` for all
* Because in each layer of a balanced BST the amount of nodes per layer is doubled, we assume that the O has a reverse geometric progression so ```O(log(n)```


## Look back

### What we've learnt



This week we learnt about binary search trees. We have a good knowledge after that about binary trees. We learned how to recognize bintrees, how to insert values, move values, remove leafs or nodes etc.



### What were the surprises



Starting the assignment, it was pretty doable until we faced difficulties with running the code. For example, in the activity for removing leafs we had some problems but then luckily we figured out that in our previous code we had made mistakes and we were not getting a parent. It has been resolved.



### What problems we've encountered



We spent a lot of our time trying to understand why it is compiling on one OS and not on others. We tried different codes but still the same.



### What was or still is unclear



Overall, everyone has a good idea of how everything works, not many things still unclear.



### How did the group perform?



The group had a good communication, not many hick-ups. Time management was pretty good, work was done in time. 