the in order and postorder traversal of a binary search tree is same and it is 1,2,3,4,n what is the height of the tree (root is at height o).? 1..n-1 2.n 3.n/2 3.n/2-1
Answers
Answer:
this one is example not the answer for this question️️️
Explanation:
Input:
in[] = {2, 1, 3}
post[] = {2, 3, 1}
Output: Root of below tree
1
/ \
2 3
Input:
in[] = {4, 8, 2, 5, 1, 6, 3, 7}
post[] = {8, 4, 5, 2, 6, 7, 3, 1}
Output: Root of below tree
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
1
/ \
[4, 8, 2, 5] [6, 3, 7
The idea is similar.
Let us see the process of constructing tree from in[] = {4, 8, 2, 5, 1, 6, 3, 7} and post[] = {8, 4, 5, 2, 6, 7, 3, 1}
1) We first find the last node in post[]. The last node is “1”, we know this value is root as root always appear in the end of postorder traversal.
2) We search “1” in in[] to find left and right subtrees of root. Everything on left of “1” in in[] is in left subtree and everything on right is in right subtree.
3) We recur the above process for following two.
….b) Recur for in[] = {6, 3, 7} and post[] = {6, 7, 3}
…….Make the created tree as right child of root.
….a) Recur for in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}.
…….Make the created tree as left child of root.
Below is the implementation of above idea. One important observation is, we recursively call for right subtree before left subtree as we decrease index of postorder index whenever we create a new node.
i hope this one will help you