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