# Week 9 - Binary Trees

## Team

Team name: Academy Award Winning, Choccy Milk Drinking, Argonian Maid Reading, Cross Dressing SIMPS In Yugoslavia With Honda Accords On The Quest For Feet

Date: 25/04/2022
yes(66%)

Members
Mihnea: Mihnea Bastea (514541)
Vlad: Vladislav Serafimov (509761)
Steve: Stephen Cruz Wright (521476)

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Vlad |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Steve |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Mihnea |

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

Assuming membership testing is done every time
| | Array | Linked List |
| ------------------ | --------- | ----------- |
| value insertion |O(n.log(n))| O(n) |
| value removal |O(n.log(n))| O(n) |
| membership testing | O(log(n)) | 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);
    
    //3 levels
    bintree_node root{2}, left{3}, right{5}, left_left{7}, right_right{11};
    root.set_left(&left);
    root.set_right(&right);
    left.set_left(&left_left);
    right.set_right(&right_right);

    //4 levels
    bintree_node root{2}, left{3}, right{5}, left_left{7}, left_left_left{11};
    root.set_left(&left);
    root.set_right(&right);
    left.set_left(&left_left);
    left_left.set_left(&left_left_left);

    //5 levels
    bintree_node root{2}, left{3}, left_left{5}, left_left_left{7}, left_left_left_left{11};
    root.set_left(&left);
    left.set_left(&left_left);
    left_left.set_left(&left_left_left);
    left_left_left.set_left(&left_left_left_left);
    
}

### Activity 3: Recognizing BSTs
In tree A the value 71 (at root->rigth->left) should be bigger than 72 (the root).
In tree B the value 84 (at root->rigth->rigth) should be bigger than 85 (at root->rigth).
Tree C is a BST.

### Activity 4: Searching for values

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

### Activity 5: Inserting values

bintree_node *bintree_node::insert(int value) {
    if (value == m_value)
        return nullptr;
    else if (value < m_value) {
        if (!has_left_child()) {
            return (m_left = new bintree_node{value, this});
        }
        m_left->insert(value);
    } else {
        if (!has_right_child())
            return (m_right = new bintree_node{value, 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, because the maximum value in a node’s left subtree cannot be greater than the minimum value in a
node’s right subtree by definition and consequently the minimum value in a node’s left subtree cannot be greater than the minimum value in a
node’s right subtree.

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

- No because that would mean it is not the smallest.

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

- By searching for the leftmost value in the binary search.

### Activity 7: Finding the minimum value

bintree_node &bintree_node::minimum() {
    auto copy = this;
    while (copy->m_left != nullptr)
        copy = copy->m_left;
    return *copy;
}

### Activity 8: Removing leafs

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        if (m_left) {
            m_parent->replace_child(this,this->m_left);
            return this;
        }
        if (m_right) {
            replace_child(m_right, nullptr);
            return m_right;
        }
    } else if (has_right_child()) {
    } else if (has_left_child()) {
    } else {
    }
}

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

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        m_parent->replace_child(this,this->m_left);
        return this;
    } else if (has_right_child()&& !has_left_child()) {
        m_parent->replace_child(this,this->m_right);
        return this;
    } else if (has_left_child() &&!has_right_child()) {
        m_parent->replace_child(this,this->m_left);
        return this;
    } else {
        // Activity 11 - this node is a full node
    }
    return nullptr;
}

### Activity 10: Moving values around

In the left tree, B ≥ A, C ≥ A, and F<=E therefore F could be a child of B, and either B or F could be the root.

In the right tree G or E could be the root because C ≥ A, E ≥ C, F ≥ G, G ≥ root ≥ E

### Activity 11: Removing full nodes

bintree_node *bintree_node::remove() {
    if (is_leaf()) {
        m_parent->replace_child(this, this->m_left);
        return this;
    } else if (has_right_child() && !has_left_child()) {
        m_parent->replace_child(this, this->m_right);
        return this;
    } else if (has_left_child() && !has_right_child()) {
        m_parent->replace_child(this, this->m_left);
        return this;
    } else {
        bintree_node *node = &m_right->minimum();
        this->m_value = node->m_value;
        node->m_parent->replace_child(node, node->m_left);
        return node;
    }
    return nullptr;
}

### Activity 12: (Un)balanced trees

Tree 1 is a complete tree balanced and symmetrical

Tree 2 is an unbalanced tree which is basically a linked list but listed backwards, in descending order, in the shape of a tree.

Tree 3 is an unbalanced tree which is basically a normal linked list in the shape of a tree in ascending order.

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

Trees are not friendly

### What were the surprises

How many tree variations exist
feet
maps

### What problems we've encountered

removing nodes

### What was or still is unclear

nothing tbh

### How did the group perform?

gg wp