Binary Tree

Code for Binary Tree Clone

#include <iostream>

// Node for the binary tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Binary Tree class
class BinaryTree {
private:
    Node* root;

    // A helper function for cloning the tree
    Node* cloneTree(Node* node) {
        if (node == nullptr) {
            return nullptr;
        }

        // Create a new node with the same data
        Node* newNode = new Node(node->data);

        // Recursively clone the left and right subtrees
        newNode->left = cloneTree(node->left);
        newNode->right = cloneTree(node->right);

        return newNode;
    }

    // A helper function for printing the tree (in-order traversal)
    void printInOrder(Node* node) {
        if (node == nullptr) {
            return;
        }
        printInOrder(node->left);
        std::cout << node->data << " ";
        printInOrder(node->right);
    }

    // A helper function for cleaning up memory (post-order traversal)
    void destroyTree(Node* node) {
        if (node == nullptr) {
            return;
        }
        destroyTree(node->left);
        destroyTree(node->right);
        delete node;
    }

public:
    // Constructor
    BinaryTree() : root(nullptr) {}

    // Destructor
    ~BinaryTree() {
        destroyTree(root);
    }

    // Insert a new node (for demonstration purposes)
    void insert(int data) {
        // Simple insertion for demonstration
        Node* newNode = new Node(data);
        if (root == nullptr) {
            root = newNode;
            return;
        }

        Node* current = root;
        while (true) {
            if (data < current->data) {
                if (current->left == nullptr) {
                    current->left = newNode;
                    return;
                }
                current = current->left;
            } else {
                if (current->right == nullptr) {
                    current->right = newNode;
                    return;
                }
                current = current->right;
            }
        }
    }

    // Public clone method
    BinaryTree clone() {
        BinaryTree newTree;
        newTree.root = cloneTree(this->root);
        return newTree;
    }

    // Public print method
    void print() {
        printInOrder(root);
        std::cout << std::endl;
    }
};

int main() {
    BinaryTree original_tree;
    original_tree.insert(50);
    original_tree.insert(30);
    original_tree.insert(70);
    original_tree.insert(20);
    original_tree.insert(40);
    original_tree.insert(60);
    original_tree.insert(80);

    std::cout << "Original Tree (In-order): ";
    original_tree.print();

    // Clone the tree
    BinaryTree cloned_tree = original_tree.clone();

    std::cout << "Cloned Tree (In-order): ";
    cloned_tree.print();

    return 0;
}