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

This is the 43rd Video of our Playlist "Binary Tree : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve a very good Binary Tree problem : Smallest String Starting From Leaf | DFS | BFS | Google | Leetcode 988 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Smallest String Starting From Leaf | DFS | BFS | Google | Leetcode 988 | codestorywithMIK
Company Tags : will update soon

Approach Summary :
### Approach 1: Depth-First Search (DFS)
- **Time Complexity (T.C):** O(n) - where n is the number of nodes in the tree. This is because each node is visited exactly once.
- **Space Complexity (S.C):** O(n) - space taken for recursion system stack. In the worst-case scenario, the recursion stack could go as deep as the number of nodes in the tree.
- **Description:**
- The algorithm performs a depth-first traversal of the tree, starting from the root.
- At each node, it appends the character corresponding to the current node's value to the string `curr`.
- If the current node is a leaf node (i.e., it has no children), it compares the resulting string `curr` with the current `result`, updating `result` if necessary.
- Recursively explores the left and right subtrees.

### Approach 2: Breadth-First Search (BFS)
- **Time Complexity (T.C):** O(n) - where n is the number of nodes in the tree. Each node is visited once in the worst-case scenario.
- **Space Complexity (S.C):** O(n) - space used by the queue to store nodes and strings.
- **Description:**
- The algorithm performs a breadth-first traversal of the tree, starting from the root.
- It uses a queue to keep track of nodes and their corresponding strings.
- At each step, it dequeues a node and its associated string from the queue.
- If the dequeued node is a leaf node, it compares the resulting string with the current `result`, updating `result` if necessary.
- Enqueues the left and right children of the dequeued node along with their corresponding strings, obtained by appending the character corresponding to the child node's value to the current string.

Both approaches achieve the same goal of finding the lexicographically smallest string formed by traversing from the root to a leaf node in the binary tree. The choice between the two approaches may depend on factors such as memory constraints or the specific characteristics of the tree.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[Ankitkumar-fzkc]

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

[hypewaali]

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

[chitranshjain]

Bhaiya gfg ki potd bhi start kariye na
Please reply

[Dynamic-ylci]

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

[Mercer_]

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

[gui-codes]

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

[chakrabarti]

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?

[Exam_Rider]

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

[aayush-E]

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 "{}";

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, "");
}
};

[DurgaShiva]

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);
}
}
}

[abcd]

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 ??

[jeehub]

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

[jkat_]

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
string
if(left!=""&&right!="" && left<right)
{
return left+string(1, root->val + 'a');;
}
else if(left!=""&&right!="" && right!=""&&right<left)
{
return right+string(1, root->val + '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?

[dayashankarlakhotia]

class Solution {
String ans=" ";
private void solve(TreeNode root, StringBuilder sb){
if(root==null) return;


if(ans.equals(" "))
ans=sb.toString();
else

solve(root.left, sb);
solve(root.right, sb);
sb.deleteCharAt(0);
}
public String smallestFromLeaf(TreeNode root){
solve(root, new StringBuilder());
return ans;
}
}
🎉❤

[ishaansharma]

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 =
string rightKaAns =

char temp = root->val + 'a';
if((leftKaAns == "" && rightKaAns != "") || (leftKaAns != "" && rightKaAns == "")){
return leftKaAns == ""? rightKaAns+temp :leftKaAns+temp;
}
return rightKaAns+temp: leftKaAns+temp ;
}

[Abhay]

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

[jayrathod]

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]