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:  

# Python3 program to convert
# binary tree to double tree

# A binary tree node has data,
# pointer to left child and a
# pointer to right child
class Node:
    def __init__(self, d):
        self.data = d
        self.left = None
        self.right = None

    # Function to convert a tree to var tree
def doubleTree(node) :
    if node == None :
            return

    # do the subtrees
    doubleTree(node.left)
    doubleTree(node.right)

    # duplicate this node to its left
    oldleft = node.left
    node.left = Node(node.data)
    node.left.left = oldleft
    
    # Given a binary tree, print its nodes in inorder
def printInorder(node) :
    
    if node == None :
            return
    printInorder(node.left)
    print(node.data,end=' ')
    printInorder(node.right)
    
# Driver Code
if __name__ == '__main__':
    
    '''
    Driver program to test the above functions */

        /* Constructed binary tree is
            1
            / \
        2     3
        / \
        4 5
    '''
    
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    print("Original tree is : ")
    printInorder(root)
    doubleTree(root)
    print()
    print("Inorder traversal of double tree is : ")
    printInorder(root)

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.