---
# System prepended metadata

title: Week 9 - Binary Trees

---

# Week 9 - Binary Trees

## Team

Team name:
Date:

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.                                             |   Yazan Tayeh 473427   |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings.                                              |    Nafiz Redwan 515199  |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |   Husam Kanoa 512881   |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data.                                                   |  Rimma Davletova 508350    |

## 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(..1.)      |
| value removal      | O(.N..) | O(..1.)      |
| membership testing | O(..1.) | 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);
}
```

### Activity 3: Recognizing BSTs
C is the binary tree

B is not a binary tree because 85 is a parent of 84
A is not a binary tree because it is not balanced

### Activity 4: Searching for values

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

### Activity 5: Inserting values

```c++
bintree_node* bintree_node::insert(int value) {
     if(value <= data){
            if(left == NULL){
                left = new Node(value);
            }else{
                left->insert(value);
            }
        }else{
            if(right == NULL){
                right = new Node(value);
            }else{
                right->insert(value);
            }
        }
}
```

### Activity 6: Properties of the minimum value

No, its not possible cos that will cause unbalance to the tree. 
no , its not possible to have a left subtree , The Root stores the minmium value if the left subtree is empty.
No , there is not .
### Activity 7: Finding the minimum value

```c++
bintree_node &bintree_node::minimum() {
    if (m_left == nullptr)
        return *this;
    return m_left->minimum();
}
```

### Activity 8: Removing leafs
```c++
bintree_node *bintree_node::remove() {
    if(m_right == nullptr && m_left == nullptr){
        m_parent->replace_child(this, nullptr);
        return this;
    }
}

```

### Activity 9: Removing nodes that have one child

```c++
bintree_node *bintree_node::remove() {
    if(m_right == nullptr && m_left == nullptr){
        m_parent->replace_child(this, nullptr);
        return this;
    }else{
        if(m_right == nullptr){
            m_parent->replace_child(this,m_left);
            return this;
        }else if(m_left == nullptr){
            m_parent->replace_child(this,m_right);
            return this;
        }
    }
}

```


### Activity 10: Moving values around

Record your answer here

### Activity 11: Removing full nodes

```c++
bintree_node *bintree_node::remove() {
    if(m_right == nullptr && m_left == nullptr){
        m_parent->replace_child(this, nullptr);
        return this;
    }else{
        if(m_right == nullptr){
            m_parent->replace_child(this,m_left);
            return this;
        }else if(m_left == nullptr){
            m_parent->replace_child(this,m_right);
            return this;
        }else{
            bintree_node &m = m_right->minimum();
            m_value = m.value();
            m.remove();
            return &m;
        }
    }
}

```

### Activity 12: (Un)balanced trees

Record your answer here

### Activity 13: Time complexity

| Operation | Time complexity (if balanced)   | Time complexity (if unbalanced) |
| --------- | --------------- | --------------- |
| Lookup    | O(log(N))          | O(N)          |
| Insert    | O(log(N))          | O(N)          |
| Remove    | O(log(N))          | O(N)          |

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### 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?





> Written with [StackEdit](https://stackedit.io/).
