Clone a Binary Tree
Given a binary tree, efficiently create copy of it.
The idea very simple – recursively traverse the binary tree in a preorder fashion, and for each encountered node, create a new node with the same data and insert a mapping from the original tree node to the new node in a hash table. After creating the mapping, recursively process its children.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <iostream> using namespace std; // A Binary Tree Node class Node { public: int data; Node* left, *right; Node(int data) { this->data = data; this->right = this->left = nullptr; } }; // Function to print the inorder traversal on a given binary tree void inorder(Node* root) { if (root == nullptr) { return; } // recur for the left subtree inorder(root->left); // print the current node's data cout << root->data << " "; // recur for the right subtree inorder(root->right); } // Recursive function to clone a binary tree Node* cloneBinaryTree(Node* root) { // base case if (root == nullptr) { return nullptr; } // create a new node with the same data as the root node Node* root_copy = new Node(root->data); // clone the left and right subtree root_copy->left = cloneBinaryTree(root->left); root_copy->right = cloneBinaryTree(root->right); // return cloned root node return root_copy; } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); Node* clone = cloneBinaryTree(root); cout << "Inorder traversal of the cloned tree: "; inorder(clone); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
// A Binary Tree Node class Node { int data; Node left, right; Node(int data) { this.data = data; } } class Main { // Function to print the inorder traversal on a given binary tree public static void inorder(Node root) { if (root == null) { return; } // recur for the left subtree inorder(root.left); // print the current node's data System.out.print(root.data + " "); // recur for the right subtree inorder(root.right); } // Recursive function to clone a binary tree public static Node cloneBinaryTree(Node root) { // base case if (root == null) { return null; } // create a new node with the same data as the root node Node root_copy = new Node(root.data); // clone the left and right subtree root_copy.left = cloneBinaryTree(root.left); root_copy.right = cloneBinaryTree(root.right); // return cloned root node return root_copy; } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); Node clone = cloneBinaryTree(root); System.out.print("Inorder traversal of the cloned tree: "); inorder(clone); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# A Binary Tree Node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Function to print the inorder traversal on a given binary tree def inorder(root): if root is None: return # recur for the left subtree inorder(root.left) # print the current node's data print(root.data, end=' ') # recur for the right subtree inorder(root.right) # Recursive function to clone a binary tree def cloneBinaryTree(root): # base case if root is None: return None # create a new node with the same data as the root node root_copy = Node(root.data) # clone the left and right subtree root_copy.left = cloneBinaryTree(root.left) root_copy.right = cloneBinaryTree(root.right) # return cloned root node return root_copy if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) clone = cloneBinaryTree(root) print('Inorder traversal of the cloned tree: ', end='') inorder(clone) |
Output:
Inorder traversal of the cloned tree: 4 2 5 1 6 3 7
Inorder traversal of the cloned tree: 4 2 5 1 6 3 7
The time complexity of the above solution is O(n), where n is the total number of nodes in the binary tree. The implicit extra space used by the solution is O(n) for the call stack.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)