# Week 9 - Binary search trees

## Team

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

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

## Activities

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

| Column 1 | Array | Linkedlist |
| --------- | ------ | ---------- |
| insertion | O(n^2) | O(1)/O(n) - (double/single) |
| Removal | O(n^2) | O(1)/O(n) - (double/single) |
| Membership test| O(Log n)| O(n) | |

### Activity 2: Recognizing BSTs

Tree C is the only Binary Search Tree since it follows all of the invariants. 

For Tree A, node 71 violates the order invariant.
For Tree B, node 84 violates the order invariant.

### Activity 3: Building a BST

2, 3, 5, 7, 11

3 layers:

     bintree_node root{ 5,
                          new bintree_node{3,
                              new bintree_node{2},
                              nullptr},
                          new bintree_node{7,
                              new bintree_node{nullptr},
                              new bintree_node{11}}
     bintree_writer::write_dot("example.dot", root);

4 layers:

     bintree_node root{ 3,
                        new bintree_node{2},
                        new bintree_node{5,
                            nullptr,
                            new bintree_node{7,
                                nullptr,
                                new bintree_node{11}}}                       
     bintree_writer::write_dot("example.dot", root);

5 layers:

     bintree_node root{ 2,
                        nullptr,
                        new bintree_node{3,
                            nullptr,
                            new bintree_node{5,
                                nullptr,
                                new bintree_node{7},
                                    nullptr,
                                    new bintree_node{11}}}                       
     bintree_writer::write_dot("example.dot", root);

### Activity 4: Searching for value

bintree_node *bintree_node::find( int value) {
      bintree_node* data=this;
    if(data!= nullptr) {
        if (m_value == value) {
            return data;
        }
            // value is greater than root's value
        else if (m_value < value) {
            return m_right->find(value);
        }
            // value is smaller than root's value
        else if (m_value > value) {
            return m_left->find(value);
        }
        else {return nullptr;}
    }
    return nullptr;
    }

### Activity 5: Inserting values

bintree_node* bintree_node::insert(int value) {
    auto *newNode = new bintree_node{value};
    bintree_node *forward = this;
    bintree_node *backward= nullptr ;
    while(forward!= nullptr){
        backward=forward;
        if(value<forward->m_value){
            forward=forward->m_left;
        }
        else if(value==forward->m_value){
            return nullptr;
        }
        else{
            forward=forward->m_right;}
    }
    if(backward==nullptr){
        backward=newNode;
    }
    else{
        if(value<backward->m_value){
            backward->set_left(newNode);}
        if(value>backward->m_value){
            backward->set_right(newNode);}
    }
    
    return backward;
}

### Activity 6: Properties of the minimum value

**Can the minimum value in a node’s left subtree be greater than the minimum value in a
node’s right subtree? Why (not)?**

No because, the left side is always smaller

**Can the node containing the minimum value have a left subtree? Why (not)?**
No because, the minimum is the minimum unless you add a new node which is smaller than the minimum.

**Which traversal strategy will lead to the node containing the minimum value of a tree?**

Keep going left untill it ends!

### Activity 7: Finding the minimum value

bintree_node &bintree_node::minimum() {
    // Activity 6
    bintree_node* current=this ;
    bintree_node* parent;
/* loop down to find the leftmost leaf */
    if(m_left == nullptr)
        return *this;
    while (current != NULL)
    {
        parent=current;
        current = current->m_left;
    }
    return *parent;
}

### Activity 8: Removing leafs

if (m_left == nullptr && m_right == nullptr) {
        // Activity 8
        // this node is a leaf node (it has no child nodes)
       bintree_node* temp=this;
      m_parent->replace_child(this, nullptr);
        return temp;
    }

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

else if (m_left == nullptr) {
        bintree_node* temp1=this;
        if(m_parent->m_left==this)
           m_parent->set_left(m_right);
        else
            m_parent->set_right(m_right);
        set_right(nullptr);
        return temp1;
    } else if (m_right == nullptr) {
        bintree_node* temp1=this;
        if(m_parent->m_left==this)
            m_parent->set_left(m_left);
        else
            m_parent->set_right(m_left);
        set_left(nullptr);
        return temp1;

### Activity 10: Moving values around

In the left tree, labels E and F are both able to be the root node. This is because F > A and F < D. The same goes for B.

For the right tree, labels G and E are both able to be the root node. This is bevause G > A and G < F. The same goes for E.

### Activity 11: Removing *full* nodes

 bintree_node* current = this;
        bintree_node* parent;
/* loop down to find the maximum of the leftmost leaf */
        if(m_left == nullptr)
            parent= this;
        while (current != nullptr)
        {
            parent=current;
            current = current->m_right;
        }
        bintree_node *tempMin;
        if(m_right== nullptr) {
           tempMin=parent;
        }
        else{
        tempMin=&m_right->minimum();
        }
        this->m_value = tempMin->m_value;
        auto node=tempMin->remove();
        return node;

### Activity 12: Performance analysis

In current inplementation, for each of the 3 opertaions: insertion, membership testing, and removal, worst case complexity is O(n).

That's beacuse in every operation we need to potentialy traverse all elements in the tree.

In a case where we can always maintain a tree that has as few levels as possible, with a constant time complexity O(1), the worst case time complexity would be equal to O(log2n) for every operation.

### Activity 13: Restoring balance (optional)

## Look back

### What we've learnt

What binary search trees are, how to implement code to add, search and remove nodes.

### What were the surprises

Deleting nodes is pretty hard to do.

### What problems we've encountered

Activity 9 was hard to do.

### What was or still is unclear

Nothing

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

Group performed well in my opinion. We met a few times and that went well. Jenny however did a hell of a good job!