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:
// Java 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
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right = null;
}
}
class BinaryTree
{
Node root;
/* 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 = new Node(node.data);
node.left.left = oldleft;
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null)
return;
printInorder(node.left);
System.out.print(node.data + " ");
printInorder(node.right);
}
/* Driver program to test the above functions */
public static void main(String args[])
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.println("Original tree is : ");
tree.printInorder(tree.root);
tree.doubleTree(tree.root);
System.out.println("");
System.out.println("Inorder traversal of double tree is : ");
tree.printInorder(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal(mayank_24)
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.