L36. Serialize and De-serialize Binary Tree | C++ | Java

Entire DSA Course: takeuforward.org/strivers-a2z...
Check our Website:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
#treeSeries #striver #placements

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@hardiksingh2814]

dp series, graph series, tree seriess.... you have just nailed in each of them...best teacher of DSA ever i found!!

[@aadeshsharma0001]

first i hate trees and after this series i am loving them

[@yt_kartik1008]

Same feeling😂

[@gandhijainamgunvantkumar6783]

Today is 3rd day of doing tree series and I am at this video. I can see that you have put so much hardwork in making these videos. I pray to god that he keep you happy everyday and all your dreams will be fulfilled.

[@sparshsharma6068]

Never Imagined learning an LC hard question concept this easily. Amazing explanation bhaiya🔥 and yes, likeeeed, shareeeed and subscribeeeeeeeed😉

[@aniketmasram6500]

Just wondering how someone like you sir comes to save us with wonderful explanation , just to remind you , can't thank you in words , you are awesome 🙌🙌🔥

[@souravanand99]

I rarely comment but your content is too clean and clear that I must say "Thanks a lot" !

[@rohan8758]

java code is starting at @12:06 timestamp, I am just searching into about & comments. Nicely explained the approach & solution.

[@ishangujarathi10]

Excellent approach to a HARD problem!!!loved it

[@mayanksharma4965]

What a lucid and easy explanation you have come through . Thanks brother

[@shreyasvishwakarma8979]

Wow, hard problem seems so easy from the way you teach Bhaiya . Nice video

[@bhaveshkumar6842]

Thank you, Striver for using white background for your code. I take screenshot and add text (as notes for myself) and the cursor can be seen against white background.

[@amishasahu1586]

Amazing series, bhiayaa. Thank you for all the efforts you put in.

[@stith_pragya]

Thank You So Much For this wonderful video...............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@knowthrvdo]

Nice playlist thank you

[@akshatgupta2916]

maza aa gya ye video dekh kr baaki itni jagah dekha same ques pta nhi nhi kya kya ratva rhe the this is simplest and according to me the best approach sirf approach dekho aur kaam khatam so simple to code

[@codingp110]

Awesome!

[@user-tk2vg5jt3l]

Thank you Bhaiya

[@beilulbilly2636]

Thank you

[@vrandakansal5940]

Thanks a lot....great explanation bhaiya🙇‍♀️🙌

[@993_anmol3]

its superb :) the only stress i am giving in your explanation is on the STL you are using and this is very great as i got to know many new STL that i never used before

[@priyanshkumar_iitd]

yeah

[@priyanshkumar_iitd]

thank you :)!!

[@prasadjambhale6670]

In serializing : while adding n to string remember to add space after n otherwise error will come

[@deepaksarvepalli2344]

Thanks for this series...🙏🙏🙏

[@rohangangwar6604]

this is the best series of trees ..and by this video seriously i learn some new concepts too and i don't know that How to use stringstream to separate comma separated strings finally i reasearch on it after watching this and also i am able to understand the concept behind the hard leetcode problem ... thank u bhaiya

[@devanshmesson2777]

Brilliant! Thank You so much striver!

[@ashutoshkumarsingh2592]

No need to add comma, we can do it with simple string?

[@himanshidafouty347]

Understood

[@avanishmaurya2034]

Nice

[@56_shivanshrahangdale10]

thanks for your efforts striver bhaiya !!

[@abhinanda7049]

understood

[@SHASHANKRUSTAGII]

Guess what i brought home No not Christmas tree, but yes striver's tree series :)

[@liftingMohit]

Happy Teacher's Day Striver Bhaiya

[@bhaveshkumar6842]

Thank you for your amazing content

[@nagavedareddy5891]

Huge respect...❤👏

[@Abhishek-do8mp]

after this explanation I don't think this is a hard category question at all.

[@shubhangichouksey96]

Thank you, striver!

[@debdhritiroy6868]

Here's another idea, if i somehow send a string containing preorder and inorder traversals, i shd be able to reconstruct it right?! But are the repeating vals of nodes a concern in this?!

[@enigmanarratives1]

i tried this you can see

[@enigmanarratives1]

class Codec { public: // Encodes a tree to a single string. string s; string serialize(TreeNode* root) { if(root==NULL) return s; preorder(root); inorder(root); return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { return maketree(pre,in); } vector pre; vector preorder(TreeNode* root){ if(root==NULL) return pre; pre.push_back(root->val); preorder(root->left); preorder(root->right); return pre; } vector in; vector inorder(TreeNode* root){ if(root==NULL) return in; inorder(root->left); in.push_back(root->val); inorder(root->right); return in; } TreeNode* maketree(vector&in,vector& pre ){ unordered_mapinM; for(int i=0;iinE || preS>preE) return NULL; TreeNode* root=new TreeNode(pre[preS]); int index= inM[root->val]; int numLeft= index-inS; root->left=help(in,inS,index-1,pre,preS+1,preS+numLeft,inM); root->right=help(in,index+1,inE,pre,preS+numLeft+1,preE,inM); return root; } }; but its not giving correct ans maybe if anyone can tell whats the mistake

[@enigmanarratives1]

@Ayush Negi wth man can u become my mentor and help with these types of problems ?

[@enigmanarratives1]

u explained everthing so precisely

[@falcon4359]

I searched for this because I wanted to take tree input like in leetcode test cases you know like they give you an array like this -> [1, 2, 3, null, 4, null] I know I can just replace null with # and deserialize it. But is there a way to do it with null, Because leetcode's Engine does it so there's obviously a way.

[@falcon4359]

@Ayush Negi I didn't understand your comment Here we are de-serializing a string. eg - "123#4#" instead of a string I wanted to deserialize an array - [1,2,3,null,4,null] On leetcode they write tree input like this [1,2,3,null,4,null] is an array of strings & they convert it to a binary tree of int data. That's what I was referring to. I found the solution on leetcode playground

[@alesblaze4745]

Thanks Mate!

[@gowreeManohar]

does anyone know how to do this problem with inorder traversal??

[@anonymousvoid6356]

Please tell me how you learnt DSA concepts !

[@only_for_fun1234r]

What do stringstream and getline working?

[@Anonymous-uj3jx]

Understood thanks :)

[@_AnkitOjha]

when i code it i am encountering with a run time error and i try to fix it but could not succeed and the error is " terminate called after throwing an instance of 'std::invalid_argument' what(): stoi " please help me out

[@anmolswarnkar7707]

instead of (data.size() == 0) use (data.size() == 2) since the empty brackets "[ ]" are considered as 2 characters.

[@_AnkitOjha]

@@anmolswarnkar7707 thanks

[@_AnkitOjha]

but does not work

[@anmolswarnkar7707]

then you must be passing a non integer (string) value to stoi() somewhere in runtime, check for different inputs where it is giving error.

[@prathamj2215]

you must be checking str as "#," and not "#"

[@Echo-Stories22]

if the root node is nullptr in serialize function we are appending "#" into the data so in deserialize function data.size() wont be equal to 0 at any cost so if that is the case when we try to construct a root node when the root node is nullptr or str == "#" we cant convert "#" into integer this throws an error so instead of writing if(data.size() ==0) return nullptr; we have to use if(str == "#") return nullptr; i hope this comment might help someone

[@devshubham5528]

still not working, leetcode error : terminate called after throwing an instance of 'std::invalid_argument' what(): stoi

[@UECAshutoshKumar]

Thank you sir

[@harshvardhansingh780]

If we take vector or any other things than what should be the data type of that things ..... because in string we can store character like #,$,€ etc to denote null but in others like vector how we can store the null value of binary tree?

[@AdityaSharma-nr7qn]

In gfg, it's vector so you can store -1 as null because there data of node is greater than Or equal to 1

[@falcon4359]

You can take a vector of string and do the same thing he did, convert str to int using stoi

[@TryingToImprove80085]

In java code in deserialize fn why are we pre-incrementing value of i to add right node?

[@timetotwice6881]

since left node is at 1index ,and right node is at 2nd index,so ++i,and then when loop gets incremented ,automatically i will be 3,so that 3rd and 4th node can be connected to queue.poll()aur root's left child

[@shreyarawatvlogs6920]

its giving runtime error on leetcode. can anyone help?

[@037_abhinavkumar3]

same ....did u find the solution?

[@shubhendughosh3886]

@@037_abhinavkumar3 for serialization use ostringstream s; for adding node val and #, use

[@ashwinbalaji26]

​@@037_abhinavkumar3 it works for me. Here is my code: typedef TreeNode Node; string serialize(TreeNode* root) { if(!root) return ""; string v = ""; queue q; q.push(root); while(!q.empty()) { auto curr = q.front(); q.pop(); if(!curr) v.append("#,"); else v.append(to_string(curr->val)+','); if(curr) { q.push(curr->left); q.push(curr->right); } } return v; } TreeNode* deserialize(string arr) { if(arr.size()==0) return nullptr; stringstream s(arr); string str; getline(s,str,','); Node* root= new Node(stoi(str)); queue q; q.push(root); while (!q.empty()){ auto curr = q.front(); q.pop(); getline(s,str,','); if(str != "#") { curr -> left = new Node(stoi(str)); q.push(curr->left); } else curr->left = nullptr; getline(s,str,','); if(str != "#") { curr -> right = new Node(stoi(str)); q.push(curr->right); } else curr -> right = nullptr; } return root; }

[@studymaterial9038]

When I'm trying to replace < ans.append("#,") > with simply < ans + "#,"> then it showing TLE, why?

[@ishanpatni9005]

Cause its a DataStructure of a seperate individual class

[@rohitkumar-gi8bo]

In C++, s.append("#") is faster than s=s+"#" because the latter creates a new string object and copies the contents of the original string into it along with the appended character. This can be slow if the original string is large. The former method simply appends the character to the existing string without creating a new object.

[@nikhilnagrale]

// short code used " "(space) instead of ","(comma) // preorder class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { return (!root) ? " #" : " " + to_string(root->val) + serialize(root->left) + serialize(root->right); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream s(data); return buildTree(s); } private: TreeNode* buildTree(istringstream& str) { string s; str >> s; if (s == "#") return NULL; TreeNode* node = new TreeNode(stoi(s)); node->left = buildTree(str); node->right = buildTree(str); return node; } };

[@jyotisingh8183]

Where is java code? Please let me know.

[@ISHARAMTEKE-ku2ll]

runtime error: member access within null pointer of type 'TreeNode' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:55:22 why it is showing ???

[@rishabhgupta1222]

check whether you have used the initial condition when tree is empty

[@037_abhinavkumar3]

same getting runtime error

[@AbhishekRanjan-wk7xp]

@@037_abhinavkumar3 remove the last inserted comma string serialize(TreeNode* root) { string s; queue q; q.push(root); while(!q.empty()) { auto it=q.front(); q.pop(); if(it==NULL) s.append("#,"); else s.append(to_string(it->val)+','); if(it!=NULL) { q.push(it->left); q.push(it->right); } } s.pop_back(); return s; }

[@shankhadeepsarkar2361]

class Codec { public: string serialize(TreeNode *root) { string result = ""; if (!root) { return result; } queue queue({ root }); while (!queue.empty()) { TreeNode *front = queue.front(); queue.pop(); if (front) { result += to_string(front->val) + ","; queue.push(front->left); queue.push(front->right); } else { result += "#,"; } } return result; } TreeNode* deserialize(string data) { if (!data.size()) { return NULL; } stringstream stream(data); getline(stream, data, ','); TreeNode *root = new TreeNode(stoi(data)); queue queue({ root }); while (!queue.empty()) { TreeNode *front = queue.front(); queue.pop(); string left, right; getline(stream, left, ','); getline(stream, right, ','); if (left == "#") { front->left = NULL; } else { front->left = new TreeNode(stoi(left)); queue.push(front->left); } if (right == "#") { front->right = NULL; } else { front->right = new TreeNode(stoi(right)); queue.push(front->right); } } return root; } };

[@mathematics7746]

awsmmmmmmmm

[@jaiminsolanki5478]

Understood!

[@051-avnee4]

Understood :) !!!

[@shubamgoswami]

completed!!!!!!!!!

[@aryansinha1818]

9:28

[@shubhammahakal1817]

OP !

[@tusharnain6652]

Anyone wondering why it's in LC hard, i mean it's not that hard.

[@lupin2753]

terminate called after throwing an instance of 'std::invalid_argument' what(): stoi what is this?????????

[@falcon4359]

You are going out of bounds from your string or vector or whatever you are using. Because of this stoi() is reading a garbage value that probably cant be converted to integer and terminating because thats an exception Maybe you are pushing your 1st element twice, because of which you travel more than your string size. It isnt possible to iterate for more than the string size inside the while loop

[@isheep9025]

deserialise fuction without STL functions /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: int toint(string s) { int i=0; int flag=1; if(s[i]=='-') { flag=-1; i=i+1; } int ans=0; int left; while(ival)+','; if(curNode != NULL){ q.push(curNode->left); q.push(curNode->right); } } return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if(data.size()==0)return NULL; queue q; int i=0; string s=""; while(data[i]!=',') { s=s+data[i]; i=i+1; } int rootval=toint(s); i=i+1; TreeNode * root=new TreeNode(rootval); q.push(root); while(!q.empty() && ileft=NULL; i=i+2; } else{ string s=""; while(data[i]!=',') { s=s+data[i]; i=i+1; } int leftval=toint(s); //coutright=NULL; i=i+2; } else{ string s=""; while(data[i]!=',') { s=s+data[i]; i=i+1; } int rightval=toint(s); i=i+1; TreeNode * rightnode=new TreeNode(rightval); p->right=rightnode; q.push(rightnode); } } return root; } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root));

[@adarshkumargupta.]

TLE dikha raha hai apka code ka...............

[@takeUforward]

kuch chote mote changes hue hongey, logically sahi hai.. discussion dekh lo

[@mayankjain2974]

stringstream op!

[@madhavgupta2002]

terminate called after throwing an instance of 'std::invalid_argument' what(): stoi

[@dikshatakyar]

in Serialize, when curNode==NULL, please check whether you've appended "#," and not "#"

[@madhavgupta2002]

@@dikshatakyar thank you

[@siddharth794]

How do str clears itself after one iteration. We are comparing value of str to #. if str has already some number then how it clears itself after every iteration

[@falcon4359]

thats because of getline, it flushes the input buffer

[@Randomuser7890]

@@falcon4359 what is input buffer?

[@falcon4359]

@@Randomuser7890 the input stream using which input if taken, it is called stdin if we use cin and scanf in c++. U should read about getline function

[@ShubhamKumar-fn5be]

C++ Solution without using the stringstream method also a beginner friendly code string serialize(TreeNode *root) { if(!root) return ""; string s = ""; queue q; q.push(root); while(!q.empty()){ TreeNode* node = q.front(); q.pop(); if(node){ s += to_string(node -> val) + ','; q.push(node -> left); q.push(node -> right); } else{ s += "null,"; } } cout

[@itsd2388]

thanks

[@arijitghosh397]

// Encodes a tree to a single string. string serialize(TreeNode* root) { string s = ""; if(!root) return s; queueq; q.push(root); while(!q.empty()){ TreeNode *curr = q.front(); q.pop(); if(!curr) s.append("null,"); else{ s += to_string(curr->val) + ','; q.push(curr->left); q.push(curr->right); } } return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if(data.size() == 0) return NULL; stringstream s(data); string str; getline(s, str, ','); TreeNode *root = new TreeNode(stoi(str)); queueq; q.push(root); while(!q.empty()){ TreeNode *curr = q.front(); q.pop(); getline(s, str, ','); if(str != "null"){ curr->left = new TreeNode(stoi(str)); q.push(curr->left); } getline(s, str, ','); if(str != "null"){ curr->right = new TreeNode(stoi(str)); q.push(curr->right); } } return root; }

[@adityan5302]

Python Solution : GFG It took me so much of time and if you also find so difficult or got halt some where refer this def serialize(root, arr): if root is None: return arr q=[root] while q!=[]: temp=q.pop(0) if temp!=None: arr.append(temp.data) else: arr.append("#") if temp!=None: q.append(temp.left) q.append(temp.right) return arr #Function to deserialize a list and construct the tree. def deSerialize(arr): if len(arr)==0: return None if arr[0]=="#": root=None else: root=Node(arr[0]) q=[root] i=1 while q!=[]: temp=q.pop(0) if arr[i]!="#": temp.left=Node(arr[i]) q.append(temp.left) else: temp.left=None i+=1 if arr[i]!="#": temp.right=Node(arr[i]) q.append(temp.right) else: temp.right=None i+=1 return root

[@MohsinKhan-mb6ht]

here you are adding left and right in parent how come they are added in root??

[@_SOHAMSAMANTA]

Java Code @12:08

[@hr4_harsh]

why the error error: no matching function for call to 'getline' getline(s,str,",");

[@piyush88890]

Third parameter is wrong, it should be ',' (single quotes)

[@rushidesai2836]

public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); serializeHelper(sb,root); return sb.toString(); } private void serializeHelper(StringBuilder sb, TreeNode node){ if(node == null){ sb.append("# "); return; } sb.append(node.val+" "); serializeHelper(sb,node.left); serializeHelper(sb,node.right); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] dataArr = data.split(" "); Queue q = new LinkedList(Arrays.asList(dataArr)); return deserializeHelper(q); } private TreeNode deserializeHelper(Queue q){ String val = q.poll(); if(val.equals("#")){ return null; } TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = deserializeHelper(q); node.right = deserializeHelper(q); return node; } } This approach is alternative. I did with preorder traversal.

[@maheshjindal2622]

java code @12:06

[@piyushacharya7696]

reach++

[@jayyy311]

💚

[@suvanshmahajan5902]

"us"

[@emgineer_ak3301]

why it gives runtime error terminate called after throwing an instance of 'std::invalid_argument' what(): stoi

[@242deepak]

Simpler Approach: class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if(root==NULL) return "n"; return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right); } int getNodeValue(int &i,string &temp,string &data){ while(data[i]!=',' && data[i]!='n' && ileft=makeTree(i,data); node->right=makeTree(i,data); return node; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { int i=0; return makeTree(i,data); } };

[@bharathkumar8807]

All are fake bruhhh....u are my only hope

[@PriyaSingh-jw9pl]

class Codec { public: void preOrder(TreeNode* root,string &s){ if(root==NULL){ s.append("#,"); return; } s.append(to_string(root->val) +','); preOrder(root->left,s); preOrder(root->right,s); } // Encodes a tree to a single string. string serialize(TreeNode* root) { string ans = ""; preOrder(root,ans); return ans; } TreeNode* preOrder(stringstream &s){ string s1; getline(s,s1,','); if(s1=="#")return NULL; TreeNode* root = new TreeNode(stoi(s1)); root->left = preOrder(s); root->right = preOrder(s); return root; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { stringstream s(data); return preOrder(s); } }; preorder

[@adarshkumargupta.]

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if(!root) return ""; string s= ""; queueq; q.push(root); while(!q.empty()){ auto cur = q.front(); q.pop(); if(cur==NULL) s.append("#,"); else s.append(to_string(cur->val)+ ','); if(cur!=NULL){ q.push(root->left); q.push(root->right); } } return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if(data.size()==0) return NULL; stringstream s(data); string str; getline(s,str,','); TreeNode* root = new TreeNode(stoi(str)); queueq; q.push(root); while(!q.empty()){ auto node = q.front(); q.pop(); getline(s,str,','); if(str=="#"){ node->left=NULL; }else{ TreeNode* leftnode = new TreeNode(stoi(str)); node->left= leftnode; q.push(leftnode); } getline(s,str,','); if(str=="#"){ node->right=NULL; }else{ TreeNode* rightnode = new TreeNode(stoi(str)); node->right = rightnode; q.push(rightnode); } } return root; } }; is code ka TLE aa raha hai

[@034_bharat8]

in encode code: use if(cur!=NULL){ q.push(cur->left); q.push(cur->right); }

[@smilenpassion]

Thank you for this amazing explanation. I was getting a numberformatexception, made a small change in java code and it is working now res.append("#") .append(",");

[@harshitjaiswal9439]

understood

[@vinittodai911]

Awesome!

[@sujan_kumar_mitra]

Understood

[@chiragbansod8252]

understood

[@rishabhgupta9846]

understood

[@roopeshn3301]

Understood

[@tanishkumar6682]

understood

[@pratikshadhole6694]

understood