DS_Homework_2_1

#include <iostream>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
#include <cmath>

using namespace std;

struct Node
{
    Node(const int& value) {
        this->value = value;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    };

    Node() {
        this->value = -1;
        this->leftChild = nullptr;
        this->rightChild = nullptr;
    };

    int value;
    Node* leftChild;
    Node* rightChild;
};

void insert(Node* node, const int& value);
void remove(Node* node, Node* parent);
tuple<Node*, Node*> find(Node* node, Node* parent, const int& value);
tuple<Node*, Node*> findMax(Node* node, Node* parent);
void postOrder(Node* node, vector<int>& result);
void inOrder(Node* node, vector<int>& result, const int& maxDepth = 100000000, const int& currentDepth = 0);
void preOrder(Node* node, vector<int>& result);
void printResult(const vector<int>& result);

int main() {
    string inputLine;
    getline(cin, inputLine);
    stringstream inputBuffer = stringstream(inputLine);
    int valueBuffer = -1;

    Node* tree = new Node();
    inputBuffer >> tree->value;

    int nodeCount = 1;
    while (inputBuffer >> valueBuffer) {
        insert(tree, valueBuffer);
        nodeCount++;
    }

    getline(cin, inputLine);
    inputBuffer = stringstream(inputLine);

    vector<int> result = vector<int>();
    postOrder(tree, result);
    printResult(result);
    cout << "\n";
    result.clear();


    while (inputBuffer >> valueBuffer) {
        tuple<Node*, Node*> deletingNode = find(tree, nullptr, valueBuffer);
        remove(get<0>(deletingNode), get<1>(deletingNode));
        nodeCount--;
    }

    int targetNodeCount = nodeCount / 2;
    int level = 0;
    int levelNodeCount = 1;
    vector<Node*> levelNodes = vector<Node*>();
    levelNodes.push_back(tree);
    while (true)
    {
        vector<Node*> newLevelNodes = vector<Node*>();
        int newLevelNodeCount = levelNodeCount;
        for (int i = 0; i < levelNodes.size(); i++) {
            if (levelNodes[i]->leftChild != nullptr) {
                newLevelNodes.push_back(levelNodes[i]->leftChild);
                newLevelNodeCount++;
            }
            if (levelNodes[i]->rightChild != nullptr) {
                newLevelNodes.push_back(levelNodes[i]->rightChild);
                newLevelNodeCount++;
            }
        }

        if (abs(targetNodeCount - levelNodeCount) < abs(targetNodeCount - newLevelNodeCount)) {
            levelNodes = newLevelNodes;
            levelNodeCount = newLevelNodeCount;
            break;
        }

        levelNodes = newLevelNodes;
        levelNodeCount = newLevelNodeCount;

        level++;
    }

    inOrder(tree, result, level);
    printResult(result);
    cout << "\n";
    result.clear();

    for (int i = 0; i < levelNodes.size(); i++) {
        preOrder(levelNodes[i], result);
    }
    printResult(result);

    return 0;
}

/// <summary>
/// Insert a node recursively into the binary search tree
/// </summary>
/// <param name="node">The current node, when starting it should be the root node</param>
/// <param name="value">The value to insert</param>
void insert(Node* node, const int& value) {
    if (value < node->value) {
        if (node->leftChild == nullptr) {
            node->leftChild = new Node(value);
        }
        else {
            insert(node->leftChild, value);
        }
    }
    else if (value > node->value) {
        if (node->rightChild == nullptr) {
            node->rightChild = new Node(value);
        }
        else {
            insert(node->rightChild, value);
        }
    }
}

void remove(Node* node, Node* parent) {
    if (node->leftChild == nullptr && node->rightChild == nullptr) {
        if (parent->leftChild == node) {
            parent->leftChild = nullptr;
        }
        else {
            parent->rightChild = nullptr;
        }
        delete node;
    }
    else if (node->leftChild != nullptr && node->rightChild != nullptr) {
        tuple<Node*, Node*> maxNode = findMax(node->leftChild, node);
        node->value = get<0>(maxNode)->value;
        remove(get<0>(maxNode), get<1>(maxNode));
    }
    else {
        Node* childNode = node->leftChild != nullptr ? node->leftChild : node->rightChild;
        node->value = childNode->value;
        node->leftChild = childNode->leftChild;
        node->rightChild = childNode->rightChild;
        delete childNode;
    }
}

/// <summary>
/// Find a node with a given value in a BST
/// </summary>
/// <param name="node">The current node, when starting it should be the root node</param>
/// <param name="value">The value to find</param>
/// <returns></returns>
tuple<Node*, Node*> find(Node* node, Node* parent, const int& value) {
    if (value < node->value) {
        return find(node->leftChild, node, value);
    }
    else if (value > node->value) {
        return find(node->rightChild, node, value);
    }
    else {
        return make_tuple(node, parent);
    }
}

tuple<Node*, Node*> findMax(Node* node, Node* parent) {
    if (node->rightChild == nullptr) {
        return make_tuple(node, parent);
    }
    else {
        return findMax(node->rightChild, node);
    }
}

void postOrder(Node* node, vector<int>& result) {
    if (node->leftChild != nullptr) {
        postOrder(node->leftChild, result);
    }
    if (node->rightChild != nullptr) {
        postOrder(node->rightChild, result);
    }
    result.push_back(node->value);
}

void inOrder(Node* node, vector<int>& result, const int& maxDepth, const int& currentDepth) {
    if (currentDepth > maxDepth) {
        return;
    }
    if (node->leftChild != nullptr) {
        inOrder(node->leftChild, result, maxDepth, currentDepth + 1);
    }
    result.push_back(node->value);
    if (node->rightChild != nullptr) {
        inOrder(node->rightChild, result, maxDepth, currentDepth + 1);
    }
}

void preOrder(Node* node, vector<int>& result) {
    result.push_back(node->value);
    if (node->leftChild != nullptr) {
        preOrder(node->leftChild, result);
    }
    if (node->rightChild != nullptr) {
        preOrder(node->rightChild, result);
    }
}

void printResult(const vector<int>& result) {
    for (int i = 0; i < result.size() - 1; i++) {
        cout << result[i] << " ";
    }
    cout << *(result.end() - 1);
}