Write a program that converts a given tree to its Double tree. To create Double tree of the given tree, create a new duplicate for each node, and insert the duplicate as the left child of the original node. 
So the tree…  

2
   / \
  1   3 

is changed to…  

2
      / \
     2   3
    /   /
   1   3
  /
 1 

And the tree 

1
          /   \
        2      3
      /  \
    4     5 

is changed to 

               1
             /   \
           1      3
          /      /
        2       3
      /  \
     2    5
    /    /
   4   5
  /   
 4     

Algorithm: Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.

Implementation:  

// C++ program to convert binary tree to double tree
#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data,
pointer to left child and a
pointer to right child */
class node
{
    public:
    int data;
    node* left;
    node* right;
};

/* function to create a new
node of tree and returns pointer */
node* newNode(int data);

/* Function to convert a tree to double tree */
void doubleTree(node* Node)
{
    node* oldLeft;
    
    if (Node == NULL) return;
    
    /* do the subtrees */
    doubleTree(Node->left);
    doubleTree(Node->right);
    
    /* duplicate this node to its left */
    oldLeft = Node->left;
    Node->left = newNode(Node->data);
    Node->left->left = oldLeft;
}

/* UTILITY FUNCTIONS TO TEST doubleTree() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    
    return(Node);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}

/* Driver code*/
int main()
{
    /* Constructed binary tree is
                1
            / \
            2 3
        / \
        4 5
    */
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    
    cout << "Inorder traversal of the original tree is \n";
    printInorder(root);
    
    doubleTree(root);
        
    cout << "\nInorder traversal of the double tree is \n";
    printInorder(root);
    
    return 0;
}

// This code is contributed by rathbhupendra

Output:  

Original tree is : 
4 2 5 1 3 
Inorder traversal of double tree is : 
4 4 2 2 5 5 1 1 3 3 

Time Complexity: O(n) where n is the number of nodes in the tree.

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.