> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/double-tree.md).

# Double Tree

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    
```

```java
class Solution {
    private static void doubleTree(Node node) {
        if (node == null)
            return;
        Node current = new Node(node.data);
        current.left = node.left;
        node.left = current;
        doubleTree(current.left);
        doubleTree(node.right);
    }
}
```