Smallest String Starting From Leaf | DFS | BFS | Google | Leetcode 988 | codestorywithMIK

[@Ankitkumar-fz3kc]

Already khud se solve kr chuka tha dfs se but bfs smjhana tha jo ki ache se smjh gaya bhaiya thank you.

[@codestorywithMIK]

❤️❤️

[@ugcwithaddi]

I was able to do it by myself. This is similar to “Sum root to leaf numbers”

[@tutuimam3381]

Amazing explanation ❤❤❤❤❤

[@gui-codes]

I am so glad I was able to solve using bfs and also dfs. 🤩

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤

[@codestorywithMIK]

Most welcome ❤️

[@chitranshjain9714]

Bhaiya gfg ki potd bhi start kariye na Please reply

[@Mercer_077]

Please explain time and space complexity in depth after writing code.Didn't understood the part where you said ignore time complexity.

[@codestorywithMIK]

Noted 👌 Will take care of this from next videos ❤️🙏

[@codestorywithMIK]

Let me try to explain it here also : I said that time complexity of the solution is O(n) because we visit all nodes in the tree. Note : n is the total nodes in tree. But i have ignore the time complexity of forming the string where we append the character in the string. curr = char + curr; This line itself is an O(length of curr) time complexity operation because we are copy the string with one more character to curr again. The worst case legth of curr can be n And in every recursion you perform this and hence O(n) is also added for each recursion call because of this Hence in worst case the TC will be O(n*n) Hope this helps ❤️🙏

[@potato._js]

Always prefer to solve without using global variables in DFS as it's a good practice, code for same without using global variable ans: class Solution { public: string f(TreeNode*root,string tmp){ if(!root) return "{}"; tmp.push_back('a'+root->val); if(!root->left && !root->right){ reverse(tmp.begin(),tmp.end()); return tmp; } return min(f(root->left,tmp),f(root->right,tmp)); } string smallestFromLeaf(TreeNode* root) { if(!root) return ""; return f(root,""); } };

[@codestorywithMIK]

Totally agree ❤️❤️ Will definitely take care of this and everyone of us must.

[@Dynamic-yl7ci]

11:40 uss line ki TC log n hogi na since were traversing upto the root node, so the max length of the string would be the height of the tree that would be log n in case of a binary tree

[@codestorywithMIK]

Actually I am assuming the maximum length of string formed will be n (yes n here refers to depth of tree) But in worst case, we can have a skew tree where the depth = n

[@Dynamic-yl7ci]

@@codestorywithMIK oh yaa fair enough its not a complete tree

[@abcd76820]

Hi mik , just a small doubt , iin your BFS approach of JAVA in your github repo ,, you have used Pair class and i think that there is no such class . If i have to use pair i have make pair class of my own . Then how your code is working without making pair class ??

[@codestorywithMIK]

Actually Leetcode provides it. I think that’s why it works. It gets submitted too

[@SriHarshaChilakapati]

The Pair class is from JavaFX. Leetcode just adds an implicit import to it.

[@dayashankarlakhotia4943]

class Solution { String ans=" "; private void solve(TreeNode root,StringBuilder sb){ if(root==null) return; sb.insert(0(char)(root.val+97)); if(root.left==null&&root.right==null) if(ans.equals(" ")) ans=sb.toString(); else ans=ans.compareTo(sb.toString())>0?sb.toString():ans; solve(root.left,sb); solve(root.right,sb); sb.deleteCharAt(0); } public String smallestFromLeaf(TreeNode root){ solve(root,new StringBuilder()); return ans; } } 🎉❤

[@wearevacationuncoverers]

today was Easy Medium

[@chakrabarti9634]

Anyone please help me if possible mik bhiya also....like I'm completely beginner in this field My problem is like I'm studying recursion now after studying basic concepts like leap of faith like function, recursion tree,time and space complexity and basic problems like 1 to n ,n to 1 , palindrome ,reverse string still I can't figure out how to solve the next problems like pascal triangle ,subset,print pattern like problem I can't even think of a proper solution so what should I do , please help me brothers.what to do next and is it okay for beginners?

[@mridul.7183]

yes it is absolutely fine for beginners and even more experienced coders. the solution is just not to loose hope and keep on practicing

[@ishaansharma6553]

dry run problems as much as possible , also try thinking of an approach normally , implement it , if it runs well and good otherwise dry run your code and try to find the mistake and fix it , if you are completely unable to think of a approach then watch the solution and dry run the solution on your own testcases where you might think it can get stuck . GoodLuck

[@chakrabarti9634]

@@mridul.7183 thank you so much.

[@chakrabarti9634]

@@ishaansharma6553 thanks a lot

[@codestorywithMIK]

Hey, that’s totally fine. You are a beginner. Go slowly and please make sure to run after bigger and harder problems at first. First build fundamentals, solve easy ones, solve medium ones and then move to harder ones. Welcome to Problem Solving World.

[@jeehub041]

Sir isme ek doubt ha jab back track hoga Dfs me tab jo character insert kia the use remove bhi toh Karna chahiye na?

[@codestorywithMIK]

We are not passing the curr string by reference. So it will automatically undo the changes done to curr as we backtrack in recursion. If we had passed the string by reference (&) , then we will have to pop the changes done to it before backtracking

[@jeehub041]

@@codestorywithMIK Acha ha got it👍

[@chitranshjain9714]

👏🏼👏🏼

[@shabananoor9423]

❤

[@DurgaShiva7574]

Hi All Wrote the code in Java, as follows, and the logic is also same to what is explained in video, but failing for test case : - root = [3,9,20,null,null,15,7] Output "abc" Expected "hud" Can anyone please guide me, thanks in advance class Solution { public static String smallest = null; public String smallestFromLeaf(TreeNode root) { compute(root,""); return smallest; } public void compute(TreeNode root, String s) { String temp = null; if(root == null) { return; } //checking for leaf nodes else if(root.left == null && root.right == null) { temp = ((char)(root.val+'a'))+s; //if current nod eis leaf, and the value is lesser than smalles seen till now if(smallest == null || temp.compareTo(smallest) < 0) { //update smallest smallest = temp; } } else { temp = ((char)(root.val+'a'))+s; compute(root.left, temp); compute(root.right, temp); } } }

[@aws_handles]

done

[@ishaansharma6553]

bhaiya i did the que with my approach but it got stuck on 66/70 where answer was bae and my o/p was be , isnt be lexicographically smaller than bae ? for reference this is my code .... string smallestFromLeaf(TreeNode* root) { if(root==NULL){ return ""; } string leftKaAns = smallestFromLeaf(root->left); string rightKaAns = smallestFromLeaf(root->right); char temp = root->val + 'a'; if((leftKaAns == "" && rightKaAns != "") || (leftKaAns != "" && rightKaAns == "")){ return leftKaAns == ""? rightKaAns+temp :leftKaAns+temp; } return leftKaAns.compare(rightKaAns)>=0? rightKaAns+temp: leftKaAns+temp ; }

[@idiomz4104]

bae and be, b is equal, check next, a and e, a is smaller, so bae is smaller lexicographically. Does bae come first in the dictionary or does be? That's what lexicographical order means, just the dictionary order. The length matters only when prefix is equal, if it was bae and baea, you would choose bae because it has the shorter length.

[@ishaansharma6553]

@@idiomz4104 thanks

[@Exam_Rider]

bro why we did not set curr back to " " ? pl tell

[@parnitasingh8431]

Yeah same doubt

[@parnitasingh8431]

Bro he is not passing curr by reference so when base condition triggered and return to the previous node there the string curr value is different

[@Exam_Rider]

@@parnitasingh8431 oh yea thanks

[@DevOpskagyaan]

Yes right. The string is not passed by reference. So when recursion rewinds back, the changes to current is undone

[@codestorywithMIK]

Thanks @parnitasingh8431 That’s absolutely correct.

[@dayashankarlakhotia4943]

c

[@Abhay14]

Bhai maine to brute approach try ki Sari node to leaf string ko vector of string me store kiya then sort kiya then 0th index ko return kr diya

[@codestorywithMIK]

Perfect 👌

[@jayrathod9271]

string="abcdefghijklmnopqrstuvwxyz" st=[] qu=[] st.append([root,string[root.val]]) while len(st) > 0 : curr,char=st.pop() if not curr.left and not curr.right: qu.append(char) if curr.left : st.append([curr.left,string[curr.left.val]+char]) if curr.right: st.append([curr.right,string[curr.right.val]+char]) qu.sort() return qu[0]

[@jkat_2]

i have written this code string smallestFromLeaf(TreeNode* root) { if(root==NULL) { return ""; } if(root->left==NULL && root->right==NULL) { return string(1, root->val + 'a');; } string left=smallestFromLeaf(root->left); string right=smallestFromLeaf(root->right); if(left!=""&&right!="" && leftval + 'a');; } else if(left!=""&&right!="" && right!=""&&rightval + 'a');; } else { return left==""?right+string(1, root->val + 'a'): left+string(1, root->val + 'a'); } } its not passing for this test case [4,0,1,1] .can you explain what changes should i made in code?

[@EB-ot8uu]

support++

[@itsme9877]

Bfs mushkil lga

[@codestorywithMIK]

Hi there, Would you share which part exactly you felt hard ? I will try to explain here ❤️

[@jayrathod9271]

string="abcdefghijklmnopqrstuvwxyz" st=[] qu=[] st.append([root,string[root.val]]) while len(st) > 0 : curr,char=st.pop() if not curr.left and not curr.right: qu.append(char) if curr.left : st.append([curr.left,string[curr.left.val]+char]) if curr.right: st.append([curr.right,string[curr.right.val]+char]) qu.sort() return qu[0]