# self doutbt

213 views
How to Construct Full Binary Tree from given preorder and postorder?

Thank you.
in DS
2

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.

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 traversals. But we can create a full binary tree using the above traversals without any ambiguity.

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

Therefore, following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

And following do not.
Postorder and Preorder.
Preorder and Level-order.
Postorder and Level-order.

For example, Preorder, Level-order, and Postorder traversals are same for the trees given in above diagram.

Preorder Traversal = AB
Postorder Traversal = BA
Level-Order Traversal = AB

So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.

2

Divyanshum29 in question , preorder and post order is given, How did you introduced preOrderMirror[]

1 vote

It is not possible to construct a general Binary Tree from preorder and postorder traversals. But if know that the Binary Tree is Full, we can construct the tree without ambiguity. Let us understand this with the help of following example.

Let us consider the two given arrays as pre[] = {1, 2, 4, 8, 9, 5, 3, 6, 7} and post[] = {8, 9, 4, 5, 2, 6, 7, 3, 1};
In pre[], 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 pre[], must be left child of root. So we know 1 is root and 2 is left child. How to find the all nodes in left subtree? We know 2 is root of all nodes in left subtree. All nodes before 2 in post[] must be in left subtree. Now we know 1 is root, elements {8, 9, 4, 5, 2} are in left subtree, and the elements {6, 7, 3} are in right subtree.

                  1
/   \
/      \
{8, 9, 4, 5, 2}     {6, 7, 3}

We recursively follow the above approach and get the following tree.

          1
/   \
2       3
/  \     /  \
4    5   6    7
/ \
8   9 
We can’t construct a full binary tree using preorder and postorder

For constructing full binary tree we must require inorder and any one of preorder or postorder
1

It is not possible to construct a general Binary Tree from preorder and postorder traversals. But if know that the Binary Tree is Full, we can construct the tree without ambiguity. Check my answer.

## Related questions

1
497 views
Given the preorder/postorder and inorder traversal of a binary tree, we can always construct a unique binary tree (I think so, correct me if I am wrong) Construct a binary tree with the nodes A, B, C such that its preorder traversal is ABC and its inorder traversal is CAB.
If for a given Binary Search Tree (BST) the pre-order traversal is $41,23,11,31,62,50,73$. Then which of the following is its post-order traversal? $11,31,23,50,73,62,41$ $31,11,23,50,41,62,73$ $11,31,50,23,73,62,41$ $11,31,23,50,62,73,41$