Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python

[@yang5843]

The fact that Java passed primitive-arrays-by-value instead of by-reference messed me up for HOURS when I was trying to get your n^2 solution to work. Python handles the postorder array as reference, so every time it popped, it popped globally.

[@murike]

What do you mean? Java primitive arrays are always pass by reference as any objects.

[@graydenhormes5829]

@@murike They may have reassigned the reference provided by the method parameter. In java this doesn't change the value pointed to by the reference, it just changes what the reference points to.

[@ancai5498]

The most tricker part of this issue, is regarding the sequence when we recursively called the helper or dfs function. As mentioned in the video, the second to last element is always the right subtree's root node if there's any. So when we write the recursive call, we should put the root->right = dfs(...) ahead of the root->left. Here is the C++ version w/o cache: int indexOfArray(const vector& v, int val) { for (int i = 0; i < v.size(); i++) { if (v[i] == val) { return i; } } // not found return -1; } TreeNode* buildTree(vector& inorder, vector& postorder) { return dfs(inorder, postorder, 0, inorder.size() - 1); } TreeNode *dfs(const vector& inorder, vector& postorder, int left, int right) { if (left > right) { return nullptr; } int rootVal = postorder.back(); postorder.pop_back(); int loffset = indexOfArray(inorder, rootVal); TreeNode *root = new TreeNode(rootVal); // second to last is always the right subtree's root node. root->right = dfs(inorder, postorder, loffset + 1, right); root->left = dfs(inorder, postorder, left, loffset - 1); return root; }

[@name_surname_1337]

thank you, your solutions are much better than the official ones

[@ishtiaqueahmed5925]

thank you so much. Just used this for my final exam!!

[@shuyinlam8541]

I think you need to explain the reason why should the right subtree be processed before the left subtree. This does not sound obvious at all until it cannot find index in inorder when postorder fails to play catch up.

[@jointcc2]

agree, and I think this is only specific to the case when you are given inorder and postorder

[@Dhanushh]

can you please elaborate more on why we should not start with constructing left subtree? when postorder fails to play catch up?

[@gilesgames8860]

It seems like you can start with left if you just slice both arrays, similar to how neetcode solved 105

[@jnayehsirine6222]

there is no intuition behind , the simple reason is , when right exist and is not null , it will be always n-2 in postorder thats why u start with right

[@Dhanushh]

It may look like the postorder sequence remain the same for right and left subtree callings but don't fall for it. The postorder sequence changes after you call the right subtree calling. You pass a different postorder sequence in left subtree calling. And you need to maintain a global postorder sequence Personally I feel how you determine the postorder sequence on calling right and left subtree is crucial aspect of this problem but often dismissed in many explanations I have seen.

[@karanssh]

For reference, here is neetcode 105: kzbin.info/www/bejne/n5nNZXyHfL9lsMU

[@MP-ny3ep]

Awesome explanation as always . Thank you

[@דניאלאביב-ו6ת]

what software are u using to draw on the screen?

[@gauravdesale47]

Great vid chief

[@yang5843]

class Solution { List list = new ArrayList(); Map map = new HashMap(); public TreeNode buildTree(int[] inorder, int[] postorder) { for (int p : postorder) list.add(0,p); for (int i=0;i r ) return null; TreeNode node = new TreeNode( list.remove(0) ); int i = map.get(node.val); node.right = dfs(i+1,r ); node.left = dfs(l,i-1); return node; } }

[@firezdog]

Nice now do one on the iterative solution with stack 😉

[@mohithadiyal6083]

Best explanation 😊

[@TheHy6xD]

Hey! Thank you for the video explanation, I finally understood how to do it recursively which is really easy. I have a suggestion, could you please not shorten code as you did on the 9th line? I think I understand what it does, however I am not really a Python developer and don't use one line expressions, so it's kinda hard to understand when someone does, especially in a tutorial. Thank you again!

[@patrickfeeney4180]

This is how I did it in Java with your way of doing it: ```Java class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { int[] postorderIdxEnd = new int[] { postorder.length - 1 }; HashMap inorderIdx = new HashMap(); for (int i = 0; i < inorder.length; i++) { inorderIdx.put(inorder[i], i); } return helper(0, inorder.length - 1, postorder, inorderIdx, postorderIdxEnd); } public TreeNode helper(int leftIdx, int rightIdx, int[] postorder, HashMap inorderIdx, int[] postorderIdxEnd) { if (leftIdx > rightIdx) return null; TreeNode root = new TreeNode(postorder[postorderIdxEnd[0]--]); int idx = inorderIdx.get(root.val); root.right = helper(idx + 1, rightIdx, postorder, inorderIdx, postorderIdxEnd); root.left = helper(leftIdx, idx - 1, postorder, inorderIdx, postorderIdxEnd); return root; } } ``` I used a single element array for the postorderIdxEnd so that the value would not change when popping back out form recursion since it's being passed as an argument.

[@uniquename2386]

I thought when we call two times recursive function the time complexity would be O(2^n) why it's O(n^2) in this case?

[@pudgewars6447]

Do you still need the answer?

[@uniquename2386]

@@pudgewars6447 Hey, probably not. Now I see that his O(n) recursive sol. just traverses the array, and in the case of O(n^2) he just finds an index which is O(n) also.

[@pudgewars6447]

@@uniquename2386 Okay , good to see you .

[@vijethkashyap151]

​@@pudgewars6447hey care to explain? I don't get how is O(n²)

[@vijethkashyap151]

Is this right? This operation takes linear time (O(n)) in the worst case. For each node, it needs to scan the entire inorder list to find the index of the root node's value. This happens at every level of the recursion, leading to a total of O(n * n) = O(n^2) time complexity.

[@shubhamjaiswal7645]

plz do this in c++

[@benzz22126]

how come this is a different channel??

[@justine-george]

Wouldn't this be easier? class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: if not inorder or not postorder: return None root = TreeNode(postorder[-1]) mid = inorder.index(root.val) root.left = self.buildTree(inorder[:mid], postorder[:mid]) root.right = self.buildTree(inorder[mid + 1:], postorder[mid:len(postorder) - 1]) return root

[@nitinpendekanti30]

The slicing and the index function make it an O(n^2) worst case doing this method. Neetcode's solution is more optimal

[@muzaffartursunov324]

Hello! kzbin.info/www/bejne/rJ6ZZHurfrpqodk Could you please explain why you declare "root.right" first and not "root.left". In my case i changed order of them like "root.left" comes first and "root.right" comes next. However, it did not work. It is working only your case. Thank you in advance!

[@kimayapanash8998]

Please teach us how to construct a file system like in windows in reactjs I asked another KZbinr and he gave an incomplete solution and stated that he cant solve the problem I really wanna learn it

[@user-le6ts6ci7h]

N-ary tree , or trie

[@stefanopalmieri9201]

You should avoid modifying the input parameters. If I was your interviewer, I would dock you for that.

[@amberfatima2777]

best solution