Construct Binary Tree from Inorder and Postorder Traversal | LeetCode 106 | C++, Java, Python3

[@smonkey001]

You the man. I love you keep TWO postorder indexes and the diff value to keep everything simple!

[@SnowDragon894163]

Hey, could you explain what dif here is? can't seem to wrap my head around it

[@smonkey001]

@@SnowDragon894163 Let say in-order[1,2,3,4,5,6,7] and post-order[1,3,2,5,7,6,4], p2 is 4, which is always the root node value. Search value 4 in the in-order array starting at i0, which is 0. The diff is how many steps it took to move from index i0 to value 4. in this case 3 steps, so diff = 3.

[@smonkey001]

@@SnowDragon894163 Write down the arrays. The key is to see it virtually that how the recursive function picks the root value, then divine the array to left and right sub-arrays. Then thing like `i0 + dff + 1` starts to make sense, it just picking the correct sub-arrays. in-order[1,2,3,4,5,6,7] => [left[1,2,3] root[4] right[5,6,7]], post-order[1,3,2,5,7,6,4] => [left[1,3,2] right[5,7,6] root[4]].

[@SnowDragon894163]

@@smonkey001 gotcha! Thanks a lot man!

[@laumatthew71]

Excellent explanation, thank you

[@KnowledgeCenter]

Thanks.

[@crankyinmv]

Thanks, as always for your analysis. I did something similar, but a lot simpler. I recursed the ranges of the tree right to left. As a result I was able to use an index into postorder which simply went right to left. I wrote it in javascript, so I could write the recursive part as an inner function which had access to inorder, postorder, and the index into postorder. I still passed in the start and end of the inorder range.

[@siddharthsingh4330]

the mapping way you talked in python, its faster also=> mapper = {} for i,v in enumerate(inorder): mapper[v] = i def rec(low,high): if low > high: return None #last element of postorder is the root in inorder root = TreeNode(postorder.pop()) mid = mapper[root.val] #call rec on the right of inorder and same for left root.right = rec(mid+1,high) root.left = rec(low,mid-1) return root return rec(0,len(inorder)-1)

[@ibhruti]

Great explanation. thank yo sir.......

[@Jesus.Christ..]

Thanks for the video. Is the time complexity O(n^2) because of index function?

[@neerajkulkarni6506]

fantastic explanation!

[@fxexile]

I hope my faculty is half as good.

[@vivkrish]

what blackboard app are you using? Thanks

[@KnowledgeCenter]

It's powerpoint.

[@jonathanlee3020]

Thank you.

[@KnowledgeCenter]

Welcome!

[@vivek.tiwary]

Could you explain this in iterative way

[@evgeni-nabokov]

3:00 How did you get p: 2, 4, 3? I can see how, but how the computer can get it?

[@DarkOceanShark]

I have the exact same doubt! How will you be able to extract that set from postorder. We all can recognize it but how will you make a computer recognize that and get that set from postorder.

[@girirajrdx7277]

thats the postOrder traversal...when we mean we visited the node ..it means that we had printed it...we need to start from root node only...we cant magically go directly to the last node.. postOrder traversal works in this way... left ..right....root ....repeat from root node we would be reaching the last node which is 2 ..when the recurssive call reaches this node ... 2 will be treated as the root ,since its left is none its right also none... we print the root...which means we visited

[@Brijeshkumar-lk5mt]

Hi sir, thanks for the great explanation. Also, make a video on the "Constructing Binary Tree from Inorder and Preorder Traversal".

[@arunprasad017]

def buildTreeRec(self,preorder,inorder, i1, i2, p1, p2): if i1>=i2 or p1>=p2: return val = preorder.pop(0) #1 root = TreeNode(val) idx = inorder.index(val) diff = idx - i1 root.left = self.buildTreeRec(preorder,inorder,i1,i1+diff, p1, p1+diff) root.right = self.buildTreeRec(preorder,inorder,i1+diff+1,i2, p1+diff+1, p2) return root def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: n = len(inorder) if not n: return None return self.buildTreeRec(preorder, inorder,0,n,0,n) Similar code to what is explained in the video with a slight change in the approach for assignment of root Comment #1(in code) - popping the first node so it doesn't get repeated during the next recursive call. If we had only done an assignment such as root = TreeNode(preorder[p1]) then the first value keeps getting repeated as the root again and again during the downstream recursive calls for the left and right sides. By doing this assignment we run into recursion depth failure error.

[@jsarvesh]

my solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: val_index_dict = { num:idx for idx, num in enumerate(inorder) } def helper( left, right): #print(left, right, postorder) if left > right: # Base case: # return empty node as leaf node's child return None else: # Recall: # definition of postorder traversal: Left, Right, Center # rebuild with reversed direction ( from right to left ) root = TreeNode( postorder.pop() ) mid = val_index_dict[root.val] # right subtree root.right = helper( mid+1, right) # left sub tree root.left = helper( left, mid-1 ) return root # ---------------------------------------------------- ## Top-down rebuild binary tree with definition #print("left, right, postorder") return helper( left = 0, right = len(inorder)-1 ) Time Complexity: O(N) Space Complexity: O(N)

[@arinjitaryan7291]

What if there are duplicates

[@raviashwin1157]

Sir how to print preoder from inorder and postorder traversal