Clone a binary tree – CS @ Kenyon

How do we make a copy of a binary tree?

Clone Function (cloneBST):

The cloneBST function takes the root of the original tree as an argument and recursively creates a copy of each node.
It first creates a new node with the same key as the current node in the original tree.
It then recursively clones the left and right subtrees.
This approach ensures that all nodes and their structure are duplicated.

// Function to clone a BST
Node* cloneBST(Node* root) {
    if (root == nullptr) {
        return nullptr;
    }

    // Create a new node with the same key as the root
    Node* clonedNode = new Node(root->key);
    
    // Recursively clone the left and right subtrees
    clonedNode->left = cloneBST(root->left);
    clonedNode->right = cloneBST(root->right);

    return clonedNode;
}