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

## 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(n) | O(n) |

### Activity 2: Constructing a binary tree



### Activity 3: Recognizing BSTs
Tree C is een BST.
Tree A is niet een BST. De waarde 71 staat aan de verkeerde kant.
Bij tree B staat nummer 83 rechtsonder nummer 84, dit zorgt ervoor dat het geen BST is.

### Activity 4: Searching for values

bintree_node *bintree_node::find(int value) {
    // Activity 4
    // TODO: return a pointer to the bintree_node that contains the value, or nullptr if the value is not found

        if(value == m_value)
        {
            return this;
        }
        else if(value < m_value && m_left != nullptr)
        {
            return m_left->find(value);
        }
        else if(value > m_value && m_right != nullptr){
            return m_right->find(value);
        }

        return nullptr;
    }

}

### Activity 5: Inserting values

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 (m_left != nullptr){
            return m_left->insert(value);
        }
        else {
            //create child
            //set child to created node
            //set child parent to this.
            this->m_left = new bintree_node(value, this);
            return this;
        }
    } else if (value > m_value){
        if (m_right != nullptr){
            return m_right->insert(value);
        }
        else {
            //create child
            //set child to created node
            //set child parent to this.
            this->m_right = new bintree_node(value, this);
            return this;
        }
    }
    return nullptr;
}

### Activity 6: Properties of the minimum value

als we door de linker subtree gaan totdat left null is, kunnen we het kleinste element vinden.
De node met de minimum waarde kan geen linker subtree hebben, dit omdat er links een kleinere waarde moet komen en die is er dus niet.

### Activity 7: Finding the minimum value

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

### Activity 8: Removing leafs

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        // Activity 8
        // this node is a leaf node (it has no child nodes)
        m_parent->replace_child(this, nullptr);
        return this;
    } else if (!has_right_child()) {
        m_parent->replace_child(this, m_left);
        return this;
        // Activity 9 - this node only has a left child
    } else if (!has_left_child()) {
        // Activity 9 - this node only has a right child
        m_parent->replace_child(this, m_right);
        return this;
    } else {
     auto& minRightNode =  m_right->minimum();
      this->m_value = minRightNode.value();
      return minRightNode.remove();


        // Activity 11 - this node is a full node
    }
    return nullptr;
}

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

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        // Activity 8
        // this node is a leaf node (it has no child nodes)
        m_parent->replace_child(this, nullptr);
        return this;
    } else if (!has_right_child()) {
        m_parent->replace_child(this, m_left);
        return this;
        // Activity 9 - this node only has a left child
    } else if (!has_left_child()) {
        // Activity 9 - this node only has a right child
        m_parent->replace_child(this, m_right);
        return this;
    } else {
     auto& minRightNode =  m_right->minimum();
      this->m_value = minRightNode.value();
      return minRightNode.remove();


        // Activity 11 - this node is a full node
    }
    return nullptr;
}

### Activity 10: Moving values around

Record your answer here

### Activity 11: Removing full nodes

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        // Activity 8
        // this node is a leaf node (it has no child nodes)
        m_parent->replace_child(this, nullptr);
        return this;
    } else if (!has_right_child()) {
        m_parent->replace_child(this, m_left);
        return this;
        // Activity 9 - this node only has a left child
    } else if (!has_left_child()) {
        // Activity 9 - this node only has a right child
        m_parent->replace_child(this, m_right);
        return this;
    } else {
     auto& minRightNode =  m_right->minimum();
      this->m_value = minRightNode.value();
      return minRightNode.remove();


        // Activity 11 - this node is a full node
    }
    return nullptr;
}

### Activity 12: (Un)balanced trees

Tree 1 is een BST. De andere twee zijn niet goed gesorteerd. tree 2 gaat van groot naar klein. Tree 3 gaat vab klein naar groot.

### Activity 13: Time complexity

| Operation | Time complexity (if balanced) | Time complexity (if unbalanced) |
| --------- | --------------- | --------------- |
| Lookup | O(logn) | O(n) |
| Insert | O(logn) | O(n) |
| Remove | O(logn) | 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/).