Binary Search Tree

BST.cpp

#include <bits/stdc++.h>
using namespace std;

/*
Memory is managed by Smart Pointers, So, Explicit delete is not necessary.
Hence, No memory leak. Check solve() for usage.
*/

struct NodeC {
    shared_ptr<NodeC> left, right;
    weak_ptr<NodeC> parent;
    int value;
    NodeC(int Value) {
        value = Value;
        parent.reset();
        left = right = nullptr;
    }
    bool is_leaf() {
        return (left == nullptr) && (right == nullptr);
    }
    shared_ptr<NodeC> successor() {
        // Smallest in Right Subtree
        // OR
        // Greatest in Left Subtree
        if (is_leaf()) return nullptr;
        shared_ptr<NodeC> result = nullptr;
        if (right != nullptr) {
            shared_ptr<NodeC> current = right;
            while (current != nullptr) {
                result = current;
                current = current->left;
            }
        } else if (left != nullptr) {
            shared_ptr<NodeC> current = left;
            while (current != nullptr) {
                result = current;
                current = current->right;
            }
        }
        return result;
    }
};

using Node = shared_ptr<NodeC>;

struct BST {
    Node root;
    BST() {
        root = nullptr;
    }
    Node insert(int value) {
        Node current = root, trailing = nullptr, parent = nullptr;
        Node new_node = make_shared<NodeC>(value);
        if (root == nullptr) {
            root = new_node;
            return new_node;
        }
        while (current != nullptr) {
            trailing = current;
            if (current->value > value)
                current = current->left;
            else
                current = current->right;
            if (current != nullptr)
                parent = current;
        }
        if (trailing == nullptr)
            trailing = new_node;
        else if (value < trailing->value)
            trailing->left = new_node;
        else
            trailing->right = new_node;
        new_node->parent = parent;
        return new_node;
    }

    Node find(int value) {
        Node current = root;
        while (current != nullptr && current->value != value)
            if (current->value > value)
                current = current->left;
            else
                current = current->right;
        return current;
    }

    void erase(Node current) {
        if (current == nullptr) return;
        if (current->is_leaf()) {
            Node parent = current->parent.lock();
            if (parent) {
                if (parent->left == current)
                    parent->left = nullptr;
                else
                    parent->right = nullptr;
            }
            return;
        }
        Node successor = current->successor();
        current->value = successor->value;
        erase(successor);
    }
};

void inorder(Node root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

void solve() {
    int n;
    cin >> n;
    BST arr;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        arr.insert(val);
    }
    cout << "\nInorder Traversal:\n";
    inorder(arr.root);
    cout << "\n";

    // Deleting Nodes
    cout << "\nErasing " << arr.root->value << "... ";
    arr.erase(arr.root);
    cout << "Done.\n";

    cout << "\nInorder Traversal:\n";
    inorder(arr.root);
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}