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.