Convert Sorted List to Binary Search Tree | Google | Flipkart | Amazon | Leetcode 109

[@JJ-tp2dd]

Simply brilliant! Below is the Java Implementation (TC: O(NlogN) Beats 100%) class Solution { public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; if(head.next == null) return new TreeNode(head.val); ListNode slow = head; ListNode fast = head; ListNode slow_prev = null; while(fast != null && fast.next != null) { slow_prev = slow; slow = slow.next; fast = fast.next.next; } //slow points to mid slow_prev.next = null; TreeNode root = new TreeNode(slow.val); root.left = sortedListToBST(head); root.right = sortedListToBST(slow.next); return root; } }

[@Whirlwind03]

Brother, found your channel randomly and now i'm hooked. Superb teaching 😍.

[@codestorywithMIK]

Awesome. Welcome to my channel. Thanks a lot ❤️❤️

[@U2011-n7w]

very good explanation

[@jogindrasingh6139]

Bhai thanku bhai koi doubt ho hi nahi sakta 100% trust hai bhai aap pe

[@bhartipatel7833]

Thanks for uploading full explanation. I have improved a lot and my interest to solve problem has also increased.

[@hameedmulani21]

You made it Hard to easy!

[@iamnoob7593]

Wow just brilliant

[@prateekmohanty8315]

Wow seriously I watch only 3 minutes of this video , and understood the complete approach , such beautifully you explain . Coded this myself . Thank you MIK

[@codestorywithMIK]

Thank you so so much ❤️❤️🙏🙏🙏

[@abhishekyadav1764]

Wow you gave your 200% very easy explanation....Thank you very much for such effort..,

[@codestorywithMIK]

❤️❤️ thank you

[@amitarya4894]

Thank you

[@DurgaShiva7574]

never thought this would be so easy... when GOD of DSA teaches, everything is just a story,,, hats off 2 u one suggestion, why we are doing the slow_prev->next = NULL, this could had been explained more in depth, like if we dont do it, then middle node will be again considered as a part of BST, i understood this concept, but, someone might had not, if u can please focus/ explain this point of view as well, will be very helpful.

[@codestorywithMIK]

Wow. This observation by you is worth appreciating. Thanks a lot for mentioning this Vishnu. And definitely i will take care of this. And thank you again for your kind words ❤️❤️❤️

[@nkd575]

Superb teaching bro ❤

[@aatish5375]

Bhaiya aap ka channel gfg ke problem statement ke comment section me randomly mil gaya tha and now i am hooked. Superb Teaching ❤

[@codestorywithMIK]

I am so glad Aatish. Thank you so much You made my day ❤️ Feel free to spread the word with your friends

[@aatish5375]

@@codestorywithMIK Ofcourse

[@SwikarP]

All the other playlists are awsome including this…great

[@shabananoor9423]

Amazingly explained

[@ashuthe1]

Amazing Explanation....I haven't seen much people who explain everything as clear as you do. Thanks for making such content :))

[@codestorywithMIK]

You made my day. Thank you so much ❤️

[@SwikarP]

The the the best

[@aatish5375]

Bhaiya aap ka 2no graph playlist best hai. Thanku ❤

[@codestorywithMIK]

Means a lot Aatish. Thanks a lot brother ❤️❤️❤️

[@thegreekgoat98]

You are really a magician bro.

[@codestorywithMIK]

Thanks a lot ❤️❤️❤️

[@molyoxide8358]

Learnt a new Thing, Really thanks a ton from bottom of my heart Bro.

[@yashaggarwal825]

I think u will cross many big youtubers one day!! you should launch your own courses or some unique content(like your videos ) . by the way love for your videos.

[@codestorywithMIK]

Thanks a lot Yash. I want to keep everything free. No paid course. Planning to make more playlists for everyone Thanks a lot for the appreciation ❤️❤️❤️

[@gagankaushik556]

thnx :)

[@MohdShahrukh-ne8nc]

Awesomeee man, one of best explanation

[@codestorywithMIK]

Thank you 😇🙏

[@MohdShahrukh-ne8nc]

@@codestorywithMIK hello sir ,i was raises a req to available the slot of topmate plz provide it

[@485_rahulkumar7]

great explanation bhaiya. stack ke histogram and top problem ke bhi video banayiye bhaiya.

[@codestorywithMIK]

Sure Rahul. Noted And thanks a lot for the appreciation ❤️❤️❤️

[@tutuimam3381]

Thanks a lot

[@arjunsolanki752]

As always great explaination bhaiya. Just a request can you make a video on "365. water and jug problem" . There is no good explaintion on that problem. Some people are solving that problem with bfs other are solving with gcd. Just a request whenever you get time please make a video on it.

[@codestorywithMIK]

Sure Arjun. Noted And Thanks a lot for your kind words ❤️

[@jayanth1191]

Bhaiya please cover graph concepts playlist as well😀

[@codestorywithMIK]

Yes. More videos coming soon

[@abhisekomkarprasad1460]

Spotted Gem

[@codestorywithMIK]

Means a lot to me ❤️🙏

[@molyoxide8358]

Solved this question in O(N) instead of O(NlogN) but used space. Code: class Solution { public: TreeNode* createBST(vector& nums, int l, int r) { if(lleft = createBST(nums, l, mid-1); root->right = createBST(nums, mid+1, r); return root; } return NULL; } TreeNode* sortedListToBST(ListNode* head) { if(head == NULL) return NULL; //Storing the LinkedList in a vector vector nums; while(head!=NULL) { nums.push_back(head->val); head = head->next; } //Calling createBST() & returning the root of created tree. return createBST(nums, 0, nums.size()-1); } };

[@codestorywithMIK]

Wonderful

[@molyoxide8358]

@@codestorywithMIK Thanks this means a lot

[@ms-ej4gd]

Amazing content but try to teach in english if possible for global audience 😀

[@hameedmulani21]

No bro, There are a lot of English solutions you can go there, Own mother tongue gives you a deeper understanding of concepts!

[@priyanshudubey2245]

Bhaiya ye hi time par upload kiya karo.

[@elakstein]

It can be solved in O(N) time and O(logN) space complexity and thats what interviewers will expect.

[@codestorywithMIK]

That will be great. Will be glad if you can also share your code with all of us. Will be happy to learn more on that 😊❤️

[@elakstein]

​@@codestorywithMIK sure buddy. // TC: O(N) SC: O(logN) class Solution { private: ListNode *head; int sizeOfList(ListNode *head){ int sz = 0; while(head){ head = head->next; sz++; } return sz; } TreeNode* bst(int left, int right){ if(left>right) return nullptr; int mid = left + (right - left)/2; TreeNode *leftT, *rightT; leftT = bst(left, mid-1); TreeNode *root = new TreeNode(head->val); head = head->next; root->left = leftT; root->right = bst(mid+1, right); return root; } public: TreeNode* sortedListToBST(ListNode* head) { int sz = sizeOfList(head); this->head = head; return bst(0, sz-1); } }; I also solved by the same approach as you. but when i read the editorial there they have mentioned this approach with better time complexity. Other approaches: // TC: O(N) , SC: O(N) class Solution { private: TreeNode* buildTree(vector& arr, int left, int right){ if(right < left) return nullptr; int mid = left + (right - left)/2; TreeNode *root = new TreeNode(arr[mid]); root->left = buildTree(arr, left, mid-1); root->right = buildTree(arr, mid+1, right); return root; } public: TreeNode* sortedListToBST(ListNode* head) { if(!head) return nullptr; vector arr; while(head){ arr.push_back(head->val); head = head->next; } return buildTree(arr, 0, arr.size()-1); } }; //=================== // TC: O(NlogN) , SC: O(logN) class Solution { private: ListNode* mid_node(ListNode* head){ ListNode *slow, *fast, *prev; ListNode *dummy = new ListNode(-1); dummy->next = head; slow = fast = dummy; while(fast && fast->next){ prev = slow; slow = slow->next; fast = fast->next->next; } if(prev) prev->next = nullptr; return slow; } public: TreeNode* sortedListToBST(ListNode* head) { if(!head) return nullptr; ListNode *mid = mid_node(head); TreeNode *root = new TreeNode(mid->val); if(mid == head) root->left = nullptr; else root->left = sortedListToBST(head); root->right = sortedListToBST(mid->next); return root; } };

[@codestorywithMIK]

Loved it. Thanks a lot ❤️❤️

[@bhuppidhamii]

please also tell 2 pointer approach of this Q's

[@alphadrones23]

but if we store the linked list into vector and create the tree using indexes then we can tradeoff with space and bring down the time complexity from nlogn to logn

[@codestorywithMIK]

Indeed. Good one Akhil. In vector we can directly access the mid element 👍🏻👍🏻👍🏻

[@RajdeepSingh-tv5pn]

The complexity will be O(N) not logn because we still require to traverse the linked list fully once.

[@abhijeetparashar9385]

Why we didn’t break 0 and 5 as well like we did in -3 and 0? Btw Amazing video like always!❤

[@codestorywithMIK]

You can definitely do that Abhijeet (slow->next = NULL) That will not impact. Just ensure that you pass slow->next to the recursion call.

[@abhijeetparashar9385]

@@codestorywithMIK Got it Sir. Thank you! 🙌🏻

[@ayushsingh7308]

Sir isko inorder sein bhi karsakttein haina?

[@madhavgupta2002]

github link not working

[@codestorywithMIK]

Thank you so much for pointing. ❤️❤️ It has been corrected now

[@kamranwarsi12b22]

is this approach good? TreeNode* solve(int start, int end, vector &arr){ if(start>end) return NULL; int mid = start+(end-start)/2; TreeNode* root = new TreeNode(arr[mid]); root->left = solve(start, mid-1, arr); root->right = solve(mid+1, end, arr); return root; } TreeNode* sortedListToBST(ListNode* head){ vector arr; ListNode* temp = head; while(temp != NULL){ arr.push_back(temp->val); temp = temp->next; } return solve(0,arr.size()-1,arr); }

[@codestorywithMIK]

Indeed this is good. But interviewer might ask alternative approaches

[@kamranwarsi12b22]

@@codestorywithMIK ohkk , then ig after this i should tell ur's approach.

[@codestorywithMIK]

@kamranwarsi12b22 yes 🙏❤️

[@27_shivamkumar32]

Bhaiya jis tarah humlog left ke liye slow- prev =Null kr rhe hai because connection tut ske....to ussi tarah humloh right ke liye kyu nhi kr rhe hai...slow-> next == Null ..??

[@27_shivamkumar32]

plzz reply bhaiya @codestorywithmik

[@learningbuddy8575]

You make things so simple!🤌🏻💯

[@_ANURAG-id1wh]

DSA == codestorywithMIK

[@sagarsahu4100]

quality content only 🤩 but it can be done in o(n)?