Doubt in the code

#1

I was not able to think of a solution so I went on to see the solution ,still not able to understand it,can you please explain what needs to be done and how???

#2

hi @Adhyayan
Pick an element from PostOrder from Last. Decrement a PostOrder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be j.
4) Call buildTree for elements before j and make the built tree as left subtree of tNode.
5) Call buildTree for elements after j and make the built tree as right subtree of tNode.
6) return tNode.

in order to understand this you should know how the inorder and postorder works
Inorder we have leftnodes-main node-rightnodes
and in postorder we have leftnodes-rightnodes-main node
so we take the last element from postorder and find it inside inorder array once we find the element we divides the ranges of left nodes and right nodes

we count the left nodes with index of the present element in inorder array.
and similar for right nodes

the we recursively call for left and right nodes

#3

@Adhyayan if you still have any doubt i can dry run an sample testcase for you.

#4

sir ,please dry run sample testcase.

#5

@Adhyayan sure
lets take the given test case
Input :
in[] = {4, 8, 2, 5, 1, 6, 3, 7}
post[] = {8, 4, 5, 2, 6, 7, 3, 1}
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.

      1
/    \

[4, 8, 2, 5] … [6, 3, 7]
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.

  1. we do the same process for left tree
    so in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}.

5)We search “2” in in[] to find left and right subtrees of root. Everything on left of “2” in in[] is in left subtree and everything on right is in right subtree.

     .1
   /    \
  2         [6, 3, 7]

/ …,…\
[4,8] … 5

repeat the same process for right tree again until there is only one remaining element in inorder and postorder arrays …

I hope this will help you understand it better.:blush::blush::blush:

#6


Sir,please comment my errors.

#7

@Adhyayan
there are few mistakes in your code
first of all you need these parameters in construct function (int[] post, int plo, int phi, int[] in, int ilo, int ihi)
so that you can virtually reduce the size of inorder array and postorder array.
and when you find index from search function you can not use it directly you need to count the number element on left and right with the help of index and then recursively call for left tree and right tree

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.