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.