# Week 9 - Binary Search [Trees]

## Team

Team name: **Group [497441]**
Date: 05/12/2021

Members: Max Thielen

| Role | Name |
| - | - |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Max Thielen |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Max Thielen |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Max Thielen |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Max Thielen |

## Activities

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


### Activity 2: Recognizing BSTs


Tree A and B infact do not adheare to the Binary Search Tree (BTS) structure. In **Tree A** the **value 71** is inserted improperly. Since 71 is less than the root of the tree (72) it should be placed on the left side of the tree. The proper placement would the the right leaf node of 61.
Moving to **Tree B**, it becomes evident that the **value 84** is missplaced. The right leaf node should be greater than where in this case 85 is greater. The correct placement would be the right leaf node of 75. Lastly, Tree C checks out and is organized properly.

### Activity 3: Building a BST

bintree_node root_3{
    1,
    nullptr,
    new bintree_node(
        5,
        new bintree_node(
            3,
            new bintree_node(2),
            nullptr
        ),
        new bintree_node(
            7,
            nullptr,
            new bintree_node(11)
        )
    )
};

bintree_node root_4{
    1,
    nullptr,
    new bintree_node(
        3,
        new bintree_node(2),
        new bintree_node
            5,
            nullptr,
            new bintree_node(
                7,
                nullptr,
                new bintree_node(11)
            )
        )
    )
};


bintree_node root_5{
    1,
    nullptr,
    new bintree_node(
        2,
        nullptr,
        new bintree_node(
            3,
            nullptr,
            new bintree_node(
                5,
                nullptr,
                new bintree_node(
                    7,
                    nullptr,
                    new bintree_node(11)
                )
            )
        )
    )
};

### Activity 4: Searching for values

bintree_node *bintree_node::find(int value) {
    if(this->value()==value){
        return this;
    }
    else if(value<this->value() && this->left() != nullptr){
        return this->m_left->find(value);
    }
    else if(value>this->value() && this->right() != nullptr){
        return this->m_right->find(value);
    }
    else return nullptr;
}

### Activity 5: Inserting values

bintree_node* bintree_node::insert(int value) {
    if(this->m_value==value) {
        return nullptr;
    }
    else if(this->m_value>value&&this->m_left == nullptr){
        this->set_left(new bintree_node(value, this));
        return this->m_left;
    }
    else if(this->m_value>value&&this->m_left != nullptr){
        return this->m_left->insert(value);
    }
    else if(this->m_value<value&&this->m_right == nullptr){
        this->set_right(new bintree_node(value, this));
        return this->m_right;
    }
    else if(this->m_value<value&&this->m_right != nullptr){
        return this->m_right->insert(value);
    }
    return nullptr;
}

### 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, since the entire right subtree is greater than the root and the entire left subree is less than the root, the every node in the left subree is less than any node in the right subtree.

* Can the node containing the minimum value have a left subtree? Why (not)?

No, in the event a node has a left subtree there is a smaller value in the tree since the left leaf of a node is less than the root.

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

A recusive function moving to the left leave node until there is no more left leaf node will return the minimum value of a tree.

### Activity 7: Finding the minimum value

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

### Activity 8: Removing leafs

if (m_left == nullptr && m_right == nullptr) {
        if(this->m_value<this->m_parent->m_value)
            this->m_parent->set_left(nullptr);
        else
            this->m_parent->set_right-(nullptr);
        return this;
    }

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

else if (m_left == nullptr) {
    if(this->m_value<this->m_parent->m_value) {
        this->m_parent->set_left(this->m_right);
        this->m_right->m_parent = this->m_parent;
    }
    else {
        this->m_parent->set_right(this->m_right);
        this->m_right->m_parent = this->m_parent;
    }
    return this;
} 
else if (m_right == nullptr) {
    if(this->m_value<this->m_parent->m_value) {
        this->m_parent->set_left(this->m_left);
        this->m_left->m_parent = this->m_parent;
    }
    else {
        this->m_parent->set_right(this->m_left);
        this->m_left->m_parent = this->m_parent;
    }
    return this;
}

### Activity 10: Moving values around
In the left tree values **B and F** can be safely copied into the root node without breaking the inequality order of the binary tree rules. Since B>A but still smaller than D due to the fact that B is smaller than root due it being on the left subtree is would hold the structural intergrady. Same goes for F since F is located in the right subtree, F>A yet still smaller than D since it is located in the left subtree of D.

In the right tree values **E and G** would be acceptible replacements for the root node. E>A cause it is located in the right sub tree of A and of course E< F cause E is located in the left subtree of the root. G is obviosly smaller than F and also greater than A making it a sutible match as well.

### Activity 11: Removing *full* nodes

else {
    m_value = m_right->minimum().m_value;
    m_right->minimum().remove();
}

### Activity 12: Performance analysis

Due to the fact the the current implementation of the binary tree is unbalanced, inserting consecutive increasing or decresing values creats a data structure **more reminicent of a linked listed** since the tree would emulated a straight line more than a tree. In this case inserting, membership testing, and removing nodes would take **O(n)** having to go through every node to reach the current leaf.
If the tree would be able to **rebalance** itself after every insertion or removal the time complexity would be **O(log(n))** instead.

### Activity 13: Restoring balance (optional)

## Look back

### What we've learnt

Binary Trees are like Linked Lists and Arrays Combined

### What were the surprises

Recursive Traversal

### What problems we've encountered

Activity 13 was too ambigious

### What was or still is unclear

Nothing

### How did the group perform?

Great, Raglan and I met on May 12th at 20:00 on Discord.