# C Program to Clone a Binary Tree

• Write a program in C to Clone a binary tree.
• Write a recursive function in C to create a duplicate binary tree.

Given a binary tree, we have to create a clone of given binary tree. We will traverse the binary tree using pre order traversal and create a clone of every node. The problem of creating a duplicate tree can be broken down to sub problems of creating duplicate sub trees. Below is the structure of binary tree nodes:

```struct node {
int data;
struct node *left;
struct node *right;
};
```

Algorithm to create a duplicate binary tree
Let "root" be the root node of binary tree.
• If root is equal to NULL, then return NULL.
• Create a new node and copy data of root node into new node.
• Recursively, create clone of left sub tree and make it left sub tree of new node.
• Recursively, create clone of right sub tree and make it right sub tree of new node.
• Return new node.
Time Complexity : O(n)

## C program to create a duplicate binary tree

```#include <stdio.h>
#include <limits.h>

struct node {
int data;
struct node *left;
struct node *right;
};

struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));

/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

/*
This function returns below tree
1
/ \
9    12
/ \    \
4  50    -7
/ \
18  9
*/
struct node* generateBTree(){
// Root Node
struct node* root =  getNewNode(1);

root->left = getNewNode(9);
root->right = getNewNode(12);

root->left->left = getNewNode(4);
root->left->right = getNewNode(50);
root->right->right = getNewNode(-7);

root->left->left->left = getNewNode(18);
root->left->left->right = getNewNode(9);

return root;
}

/* Returns a tree which is exact copy of passed tree */
struct node* cloneBinaryTree(struct node *root){
if(root == NULL)
return NULL;
/* create a copy of root node */
struct node* newNode = getNewNode(root->data);
/* Recursively create clone of left and right sub tree */
newNode->left = cloneBinaryTree(root->left);
newNode->right = cloneBinaryTree(root->right);
/* Return root of cloned tree */
return newNode;
}

/*
Prints inOrder Traversal of a binary tree
*/
void inOrderTraversal(struct node *nodeptr){
if(nodeptr != NULL){
/* First, recursively prints in Order traversal of left sub-tree */
inOrderTraversal(nodeptr->left);
/* Prints current node */
printf("%d ", nodeptr->data);
/* Recursively prints in Order traversal of right sub-tree */
inOrderTraversal(nodeptr->right);
}
}
int main() {
struct node *clone, *root = generateBTree();

/*InOrder traversal of original tree */
printf("Original Tree\n");
inOrderTraversal(root);

clone = cloneBinaryTree(root);

/*InOrder traversal of clone tree */
printf("\nClone Tree\n");
inOrderTraversal(clone);

getchar();
return 0;
}
```
Output
```Original Tree
18 4 9 9 50 1 12 -7
Clone Tree
18 4 9 9 50 1 12 -7
```