Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.
A Full Binary Tree is a binary tree where every node has either 0 or 2 children.
Note: It is not possible to construct a general binary tree using these two traversal. But we can create a full binary tree using the above traversals without any ambiguity. For more details refer to this article.
Examples:
Input : preOrder[] = {1,2,4,5,3,6,7} preOrderMirror[] = {1,3,7,6,2,5,4} Output : 1 / 2 3 / / 4 5 6 7
-
Method 1: Let us consider the two given arrays as preOrder[] = {1, 2, 4, 5, 3, 6, 7} and preOrderMirror[] = {1 ,3 ,7 ,6 ,2 ,5 ,4}.
In both preOrder[] and preOrderMirror[], the leftmost element is root of tree. Since the tree is full and array size is more than 1. The value next to 1 in preOrder[], must be left child of root and value next to 1 in preOrderMirror[] must be right child of root. So we know 1 is root and 2 is left child and 3 is the right child. How to find the all nodes in left subtree? We know 2 is root of all nodes in left subtree and 3 is root of all nodes in right subtree. All nodes from and 2 in preOrderMirror[] must be in left subtree of root node 1 and all node after 3 and before 2 in preOrderMirror[] must be in right subtree of root node 1. Now we know 1 is root, elements {2, 5, 4} are in left subtree, and the elements {3, 7, 6} are in the right subtree.1 / / {2,5,4} {3,7,6}
We will recursively follow the above approach and get the below tree:
1 / 2 3 / / 4 5 6 7
Below is the implementation of above approach:
C++
// C++ program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
#include<bits/stdc++.h>
using
namespace
std;
// A Binary Tree Node
struct
Node
{
int
data;
struct
Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(
int
data)
{
Node *temp =
new
Node;
temp->data = data;
temp->left = temp->right = NULL;
return
temp;
}
// A utility function to print inorder traversal
// of a Binary Tree
void
printInorder(Node* node)
{
if
(node == NULL)
return
;
printInorder(node->left);
printf
(
"%d "
, node->data);
printInorder(node->right);
}
// A recursive function to construct Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
Node* constructBinaryTreeUtil(
int
pre[],
int
preM[],
int
&preIndex,
int
l,
int
h,
int
size)
{
// Base case
if
(preIndex >= size || l > h)
return
NULL;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
Node* root = newNode(pre[preIndex]);
++(preIndex);
// If the current subarry has only one element,
// no need to recur
if
(l == h)
return
root;
// Search the next element of pre[] in preM[]
int
i;
for
(i = l; i <= h; ++i)
if
(pre[preIndex] == preM[i])
break
;
// construct left and right subtrees recursively
if
(i <= h)
{
root->left = constructBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root->right = constructBinaryTreeUtil (pre, preM,
preIndex, l+1, i-1, size);
}
// return root
return
root;
}
// function to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
void
constructBinaryTree(Node* root,
int
pre[],
int
preMirror[],
int
size)
{
int
preIndex = 0;
int
preMIndex = 0;
root = constructBinaryTreeUtil(pre,preMirror,
preIndex,0,size-1,size);
printInorder(root);
}
// Driver program to test above functions
int
main()
{
int
preOrder[] = {1,2,4,5,3,6,7};
int
preOrderMirror[] = {1,3,7,6,2,5,4};
int
size =
sizeof
(preOrder)/
sizeof
(preOrder[0]);
Node* root =
new
Node;
constructBinaryTree(root,preOrder,preOrderMirror,size);
return
0;
}
Java
// Java program to construct full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
class
GFG
{
// A Binary Tree Node
static
class
Node
{
int
data;
Node left, right;
};
static
class
INT
{
int
a;
INT(
int
a){
this
.a=a;}
}
// Utility function to create a new tree node
static
Node newNode(
int
data)
{
Node temp =
new
Node();
temp.data = data;
temp.left = temp.right =
null
;
return
temp;
}
// A utility function to print inorder traversal
// of a Binary Tree
static
void
printInorder(Node node)
{
if
(node ==
null
)
return
;
printInorder(node.left);
System.out.printf(
"%d "
, node.data);
printInorder(node.right);
}
// A recursive function to con Full binary tree
// from pre[] and preM[]. preIndex is used to keep
// track of index in pre[]. l is low index and h is high
//index for the current subarray in preM[]
static
Node conBinaryTreeUtil(
int
pre[],
int
preM[],
INT preIndex,
int
l,
int
h,
int
size)
{
// Base case
if
(preIndex.a >= size || l > h)
return
null
;
// The first node in preorder traversal is root.
// So take the node at preIndex from preorder and
// make it root, and increment preIndex
Node root = newNode(pre[preIndex.a]);
++(preIndex.a);
// If the current subarry has only one element,
// no need to recur
if
(l == h)
return
root;
// Search the next element of pre[] in preM[]
int
i;
for
(i = l; i <= h; ++i)
if
(pre[preIndex.a] == preM[i])
break
;
// con left and right subtrees recursively
if
(i <= h)
{
root.left = conBinaryTreeUtil (pre, preM,
preIndex, i, h, size);
root.right = conBinaryTreeUtil (pre, preM,
preIndex, l +
1
, i -
1
, size);
}
// return root
return
root;
}
// function to con full binary tree
// using its preorder traversal and preorder
// traversal of its mirror tree
static
void
conBinaryTree(Node root,
int
pre[],
int
preMirror[],
int
size)
{
INT preIndex =
new
INT(
0
);
int
preMIndex =
0
;
root = conBinaryTreeUtil(pre,preMirror,
preIndex,
0
, size -
1
, size);
printInorder(root);
}
// Driver code
public
static
void
main(String args[])
{
int
preOrder[] = {
1
,
2
,
4
,
5
,
3
,
6
,
7
};
int
preOrderMirror[] = {
1
,
3
,
7
,
6
,
2
,
5
,
4
};
int
size = preOrder.length;
Node root =
new
Node();
conBinaryTree(root,preOrder,preOrderMirror,size);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to construct full binary
# tree using its preorder traversal and
# preorder traversal of its mirror tree
# Utility function to create a new tree node
class
newNode:
def
__init__(
self
,data):
self
.data
=
data
self
.left
=
self
.right
=
None
# A utility function to pr inorder
# traversal of a Binary Tree
def
prInorder(node):
if
(node
=
=
None
) :
return
prInorder(node.left)
print
(node.data, end
=
" "
)
prInorder(node.right)
# A recursive function to construct Full
# binary tree from pre[] and preM[].
# preIndex is used to keep track of index
# in pre[]. l is low index and h is high
# index for the current subarray in preM[]
def
constructBinaryTreeUtil(pre, preM, preIndex,
l, h, size):
# Base case
if
(preIndex >
=
size
or
l > h) :
return
None
, preIndex
# The first node in preorder traversal
# is root. So take the node at preIndex
# from preorder and make it root, and
# increment preIndex
root
=
newNode(pre[preIndex])
preIndex
+
=
1
# If the current subarry has only
# one element, no need to recur
if
(l
=
=
h):
return
root, preIndex
# Search the next element of
# pre[] in preM[]
i
=
0
for
i
in
range
(l, h
+
1
):
if
(pre[preIndex]
=
=
preM[i]):
break
# construct left and right subtrees
# recursively
if
(i <
=
h):
root.left, preIndex
=
constructBinaryTreeUtil(pre, preM, preIndex,
i, h, size)
root.right, preIndex
=
constructBinaryTreeUtil(pre, preM, preIndex,
l
+
1
, i
-
1
, size)
# return root
return
root, preIndex
# function to construct full binary tree
# using its preorder traversal and preorder
# traversal of its mirror tree
def
constructBinaryTree(root, pre, preMirror, size):
preIndex
=
0
preMIndex
=
0
root, x
=
constructBinaryTreeUtil(pre, preMirror, preIndex,
0
, size
-
1
, size)
prInorder(root)
# Driver code
if
__name__
=
=
"__main__"
:
preOrder
=
[
1
,
2
,
4
,
5
,
3
,
6
,
7
]
preOrderMirror
=
[
1
,
3
,
7
,
6
,
2
,
5
,
4
]
size
=
7
root
=
newNode(
0
)
constructBinaryTree(root, preOrder,
preOrderMirror, size)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
Output:
4 2 5 1 6 3 7
- Method 2: If we observe carefully, then reverse of the Preorder traversal of mirror tree will be the Postorder traversal of original tree. We can construct the tree from given Preorder and Postorder traversals in a similar manner as above. You can refer to this article on how to Construct Full Binary Tree from given preorder and postorder traversals.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments