Binary Search Tree from Preorder traversal | LeetCode 1008 | C++, Java, Python | May Challenge 24

[@ashwinvarma9349]

This is why I prefer your channel sir! Your all explanations are epic!

[@KnowledgeCenter]

Wow, thanks!

[@nishantboro4728]

0:56 That visualization of pre-order traversal is really top notch!

[@KnowledgeCenter]

Thanks.

[@faisalrafi2078]

Your way of explanation is crisp and clear. Liked your way of coding, simple and easily understandable

[@Shubham-ny2ce]

The moment I think you are starting to write the code...you end up by compiling it .... Oh... No ... You are very clear with you thoughts. ...

[@amarjeetyadav7783]

Big Fan of you. Awesome explanation.

[@KnowledgeCenter]

Thanks a lot.

[@salimzhulkhrni1610]

great explanation :) could you please provide the time and space complexity as well?

[@indranilthakur3605]

Is there to put an indentation in the recursive call to understand the flow of calls?

[@KnowledgeCenter]

You can put logs in build_tree() function along with indices l and r to know what order the tree is built.

[@KnowledgeCenter]

Share your solutions in the comments section below.

[@PhoenixRisingFromAshes471]

sir what is the time complexity of this solution...please please tell

[@KnowledgeCenter]

Time Complexity = O(n), where n = number of nodes in BST or number of elements in preorder array.

[@PhoenixRisingFromAshes471]

@@KnowledgeCenter thanks sir thanks a lot :)

[@Shubham-ny2ce]

There is a problem of building BT given parent array.. Can you explain it?

[@KnowledgeCenter]

Is the error msg coming from LeetCode side, Because there is no parent array in problem. If so, the possible cause can be your output is incorrect. For example- If output is this array [8,5,10,1,7,null,12]. It represents a valid tree.8 is root, next 2 elements are its 2 childs 5 & 10. At 3rd level there can be max 4 nodes, so 1st 2 nodes are 1 & 7, 3rd node is NULL, and 4th node is 12. So, the representation is valid. Lets take an example of invalid array: [1, 2, null, 3, 4, 5, 6] Here 1 is root, 2 and null at 2nd level. So, 3rd level can have only 2 nodes. But array says 4 nodes 3,4, 5 , 6. 3 and 4 are children of 2, and 5,6 are children of null.

[@Shubham-ny2ce]

@@KnowledgeCenter sorry... I was not talking about this problem ... You explained it very well.... I was talking about another problem , where I was given parent array and we have to make BT from it... That I found hard to understand...

[@vrindakakkar8752]

wrote similar code but am getting runtime error TreeNode* funct(vector& preorder, int left, int right){ if(preorder.size() == 0) return NULL; TreeNode* root = new TreeNode(preorder[left]); if(preorder.size() == 1 || left == right) return root; if(left > right) return NULL; int idx = left+1; while(idx val) idx++; root->left = funct(preorder,left+1, idx-1); root->right = funct(preorder,idx, right); return root; } TreeNode* bstFromPreorder(vector& preorder) { return funct(preorder, 0, preorder.size()-1); }

[@KnowledgeCenter]

Move the following check to top, before creating TreeNode(preorder[left]): if(left > right) return NULL; if left is invalid index, preorder[left] will throw error.

[@vrindakakkar8752]

@@KnowledgeCenter Thank you Sir !

[@williamwambua7710]

great content as usual.

[@KnowledgeCenter]

Thanks.