# 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

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

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

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

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

### Activity 8: Removing leafs

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

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

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/).