---
# System prepended metadata

title: Week 9 - Binary Trees

---

# 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);
}

```
![](https://i.imgur.com/vr7ltVS.png)
#### 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);
}

```
![](https://i.imgur.com/omwmw66.png)
#### 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);
}
```
![](https://i.imgur.com/jlhJrda.png)

### 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:
![](https://i.imgur.com/3wHoX36.png)
Tree two:
![](https://i.imgur.com/KhK3tOJ.png)
Tree three:
![](https://i.imgur.com/9tR3Qzi.png)

* 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.


