# Week 9 - Binary Trees
Team
Members:

Member one Andreas Andreou
Member two Iasonas Ilias Kapetanidis
Date: day month 2023 | |

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(n) | | value removal | O(n) | O(log(n)) | | membership testing | O(n) | O(n) |

### Activity 2: Recognizing BSTs

The first tree is not correct because of the value 71 is not greater than the root of the tree.
The second tree is wrong because of the value 84 it should have been bigger than 85
### Activity 3: Searching for values

bool bintree::contains(int value) const {
    // TODO (Activity 3) - find out if the tree contains the value
    //  return true if the value is in the tree, false otherwise
    (void) value;
    if (m_root == nullptr) {
        return false;  // valuei not found in the tree tree is empty
    }

    const bintree_node* current = m_root;
    while (current != nullptr) {
        if (current->value() == value) {
            return true;  // cvalue found in the curent node
        } else if (value < current->value()) {
            current = current->left();  //  in the left 
        } else {
            current = current->right();  //  in the right 
        }
    }

    return false;  //  not found in the tree
}

### Activity 4: Inserting values

bool bintree::insert(int value) {
    if (m_root == nullptr) {
        // Let the sentinel node point to the root
        m_sentinel.m_left = m_root = new bintree_node{value};
        m_count = 1;
        return true;
    } else {
        // the tree already contains some nodes

        // TODO (Activity 4) - insert the value into the tree
        //  move through the tree from the root to the node where the new node should be inserted
        //  If the value is already in the tree, return false, otherwise insert a new bintree_node
        //  at the right place, increment the count, and return true
        // The tree already contains some nodes
        bintree_node* current = const_cast<bintree_node*>(m_root);
        while (true) {
            if (value == current->value()) {
                return false;  // Value is already in the tree, return false
            } else if (value < current->value()) {
                if (current->left() == nullptr) {
                    current->m_left = new bintree_node{value};
                    m_count=m_count+1;
                    return true;  // Value inserted successfully, return true
                }
                else {
                    current = const_cast<bintree_node*>(current->left());  // Move to the left subtree
                }
            } else {
                if (current->right() == nullptr) {
                    current->m_right = new bintree_node{value};
                    m_count=m_count+1;
                    return true;  // Value inserted successfully, return true
                } else {
                    current = const_cast<bintree_node*>(current->right());  // Move to the right subtree
                }}
        }}
    return false;
}

### Activity 5: Removing leafs

void bintree::remove_leaf(bintree_node* node, bintree_node* parent) {
    if (!parent->is_child(node))
        throw std::invalid_argument("parent is not the parent of the node");

    if (parent == nullptr) {
        // Removing the root node
        m_root = nullptr;
        m_sentinel.m_left = nullptr;
    } else {
        parent->replace_child(node, nullptr);
    }

    delete node;
    m_count--;
}

void bintree::remove_half_node(bintree_node* node, bintree_node* parent) {
    if (!parent->is_child(node))
        throw std::invalid_argument("parent is not the parent of the node");

    bintree_node* child = nullptr;
    if (node->has_left_child()) {
        child = const_cast<bintree_node*>(node->left());
    } else if (node->has_right_child()) {
        child = const_cast<bintree_node*>(node->right());
    }

    if (parent == nullptr) {
        // Removing the root node
        m_root = child;
        m_sentinel.m_left = child;
    } else {
        parent->replace_child(node, child);
    }

    delete node;
    m_count--;
}

### Activity 6: Moving values around
•All values in the root’s left subtree are less than or equal to the root’s value.
• All values in the root’s right subtree are greater than or equal to the root’s value. • The left and right subtree are both sorted.
First tree Left
A < D A< B C< B
First tree Right
D>A E>F G>E
On the first tree is G

Second Tree Left
A< F A>B A< C C>D C< E
Second Right
F>G F< J G< H
On the second tree is J or H
### Activity 7: Finding the smallest and greatest values

int value1(const bintree_node* root) {
   while (root->has_left_node()) {
       root = root->left();
   }
   return root->value();
}

int value3(const bintree_node* root) {
   while (root->has_right_node()) {
       root = root->right();
   }
   while (root->has_left_node()) {
       root = root->left();
   }
   return root->value();
}

Value one searches for the smallest.It goes through the left side of the tree
Value three searches for the biggest.It goes through the right side
### Activity 8: Removing full nodes

void bintree::remove_full_node(bintree_node *node) {
    bintree_node* successor = const_cast<bintree_node*>(node->right());
    while (successor->has_left_child()) {
        successor = const_cast<bintree_node*>(successor->left());
    }

    // Replace the value of the node with the value of the successor
    node->m_value = successor->value();

    // Remove the successor node
    if (successor->is_leaf()) {
        remove_leaf(successor, nullptr);
    } else {
        remove_half_node(successor, nullptr);
    }
} ```
### Activity 9: Cleaning up

void bintree::destruct_subtree(bintree_node* root) {
// TODO (Activity 9) - destruct the subtree rooted at root
if (root == nullptr) return;

destruct_subtree(const_cast<bintree_node*>(root->left()));
destruct_subtree(const_cast<bintree_node*>(root->right()));
delete root;
}

bool bintree::remove(int value) {
bintree_node* parent = nullptr;
bintree_node* current = m_root;

// Search for the node with the given value
while (current != nullptr) {
if (value == current->value()) {
// Node found, perform the removal based on its type
if (current->is_leaf()) {
remove_leaf(current, parent);
} else if (current->is_full()) {
remove_full_node(current);
} else {
remove_half_node(current, parent);
}
return true; // Node removed successfully
} else if (value < current->value()) {
parent = current;
current = const_cast<bintree_node*>(current->left());
} else {
parent = current;
current = const_cast<bintree_node*>(current->right());
}
}

return false; // Node not found in the tree
}

### Activity 10: (Un)balanced trees

bintree bst;
std::ifstream file1("numbers1.txt");
std::ifstream file2("numbers2.txt");
std::ifstream file3("numbers3.txt");

int number;
while (file1 >> number) {
bst.insert(number);
}

while (file2 >> number) {
bst.insert(number);
}

while (file3 >> number) {
bst.insert(number);
}

// Export BST to .dot file
std::ofstream dotFile("bst.dot");
bintree_writer::write_dot(bst, dotFile);

### Activity 11: 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?