Serialize and Deserialize a Binary Tree

[@IDeserve]

Dear Friends, If you like our content and would like us to continue making great content for you, please spread the word about IDeserve. A share/appreciation from you on social network would mean the world to us! Also, do like our Facebook page: facebook.com/IDeserve.co.in :) Thanks, -Team IDeserve.

[@TheGreatOne428]

your code is not going to work because you are not passing the value of index to the function

[@DivyanshuBansal]

int index is declared globally, so it will work.

[@urge-bull]

First i was thinking this question is tough...but when i saw your tutorial in comment section of geekforgeeks i found it was the easiest question on trees.Thanks to you... i was surely clear after watching this videos that what i have to do to approch solution.

[@IDeserve]

You are welcome Ritik!

[@divjose90]

Mind blown. Best explanation and visualization on Recursive call I have come across till date. Keep it up! Looking forward to more videos.

[@IDeserve]

Thanks Divya!

[@saisrikar7987]

Can anyone else be more clearer than this!!! What an explanation!!!..Loved it!!..Hope u make more videos!!!

[@IDeserve]

Thank you so much for your kind words Sai 😀

[@viralmehta2542]

appreciate the efforts to explain in such such great details!!

[@IDeserve]

Thanks Viral!

[@learnsharegrow7294]

Algorithm made easy with this video. Thanks.

[@IDeserve]

Thanks Waseem!

[@piyushsharma1638]

Easiest way of explanation, thanks for making clear.

[@IDeserve]

Thanks Piyush for your kind words!

[@socialkeviv5444]

I loved the serialise logic. ThankYou IDeserve. deserialise can be easy, something like below. Pseudocode // start=0; end=arr.length-1; deserialise(arr, start, end) { if(arr[left]==-1) return null; mid=start+(end-start)/2; new node root root->info=arr[start]; root-left= deserialise(arr, start +1, mid); root-right=deserialise(arr, mid+1, end); return root; } //

[@abhishekkeer1520]

what a explaination .thanks IDeserve ,you deserve more like.

[@IDeserve]

Thanks Abhishek!

[@AviatorBro]

Clear and precise explanation. Thank you

[@IDeserve]

Thanks Amartya!

[@akhilbhardwaj7733]

tough question , but explained nicely

[@hydara.r.7003]

My GOD what an excellent Explanation!

[@IDeserve]

Thank you so much for your kind words Hydar!

[@humanbeing496]

great job explaining. appreciate it.

[@IDeserve]

Thanks!

[@ahmedrbii346]

@@IDeserve Why did you stop downloading videos on your channel? The last video was downloaded was in 2016

[@congdoan2006]

It's such an thorough explanation. However for the base case ( i.e. step 1 ), "index == array.size()" test is not needed because "index" only reaches the array size when all the function calls complete and return ( i.e. after the very first function call returns ).

[@MuhammadH]

how can you do this without using a global variable index (stateless) ?

[@shubhamchopra5518]

pass index also in the recursive call.

[@BB31307]

Hi there! All the way from GFG. so i was getting this Segmentation fault without this line "pre_index %= Arr.size();". For multiple test case the new_index starts from previous value. So that's the reason we are adding this line! So, is that so or anything else. Just wanted more info.

[@preetisaroha3118]

Nice explanation!! Thanks for your efforts.

[@IDeserve]

Thanks Preeti!

[@MyLifeMyWorld08]

Excellent explanation indeed !

[@IDeserve]

Thanks Jitendra!

[@jakubfraczek1208]

Thanks, helped me a lot!

[@SushilRakhonde]

There is bug in this programme, if condition in the deserialize method, if index greater than equal to array.size() then you should return immediately, else will throw exception

[@SR-we1vl]

Well Delimiter used to identify "null" should be used as some random character in place of -1, cuz it will fail in case of negative numbers, viz. tree containing -1 as the value of the Tree node.

[@ytuser659]

Brilliant! Thank you!

[@rahuljha8038]

you guys are doing great job ........ please make a video to merge n sorted linked list using heap with code in c++

[@IDeserve]

Thanks Ravi :) As per your request, we will soon create a video on the requested topic. We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@rahuljha8038]

yeah sure

[@IDeserve]

Thanks Rahul.

[@dangahng9911]

Excellent!

[@siddheshshirsat6904]

In the deserialize() implementation, is there a way to not have variable index as global (or static to the method)? Having global variables might put the limitation of not being able to run the method concurrently in different threads.

[@MrAditya4997]

You can just remove the first element of the array after processing it. So element at 0 index at any time should be current element to process. No need to keeping track of index variables (if you can modify the given array)

[@justinejose5111]

Pass idx as an argument and pass it by reference, so that it will keep updating. (Talking about C++)

[@JJ-Bond]

so this deserialization uses index as a global variable to keep track of the states, do u know if there's a way that can avoid this? thanks

[@ashwani6360]

you can use a queue instead of array; and the base case will be to return NULL when queue is empty or q.front()==-1

[@prabhakarp9861]

Thought we need atleast two traversals inorder + (pre-order / postoder) to serialising the exact tree. May be i am missing something

[@JJ-Bond]

good stuff starts at 10:36

[@aashitaramteke6726]

Great!!!!!!!!!!!!

[@IDeserve]

Thanks Ashita!

[@arpit35007]

Will this approach work if there are duplicates in the tree.

[@3hurricane4mark7]

Awesome! Walking the tree is the best way to understand recursive algorithm. I notice that by using -1 to denote null, and your code does not show value comparision, I assume it could only work for positive integers.

[@prashantbhanarkar3280]

proof of correctness for serialization?

[@RAVIKUMAR-ef4wo]

what an explanation!!!

[@IDeserve]

Thank you so much for your kind words Ravi!

[@rajranjan750]

Is this solution correct My Approach If we make array reperesentation of a tree then we know that for any index the left child will be at 2*index and the right child will be at 2*index+1 so public static void serializeTree(TreeNode node,int[] arr,int index){ if(node==null){ return; } arr[index]=node.data; serializeTree(node.left, arr, 2*index); serializeTree(node.right, arr, 2*index+1); } public static TreeNode deserializeTree(int[] arr,TreeNode node,int index){ if(arr[index]==0){ return null; } node = new TreeNode(arr[index]); node.left=deserializeTree(arr, node, 2*index); node.right=deserializeTree(arr, node, 2*index+1); return node; }

[@Kriishna47]

I GUESS THIS WILL WORK OF COMPLETE BINARY TREE, BUT NOT FOR binary tree.

[@ZiiiP2142]

Raj Ranjan That idea should work as well.

[@adicool00]

What if the node is a negative value?

[@uploder247]

Use generics then and add a character X when value is not present. You can send both preorder and inorder to construct the tree back.

[@virendrasinghbais9028]

very helpful. thankx

[@tonyriddle7646]

im having segmentation fault... anyone ? which line? /* A binary tree node has data, pointer to left child and a pointer to right child struct Node { int data; Node* left; Node* right; }; */ void preorder(Node *root, vector& res){ if(root == nullptr){ res.push_back(-1); return; } res.push_back(root->data); // cout data left, res); preorder(root->right, res); } vector serialize(Node *root){ //Your code here if(root == nullptr) return {-1}; vector res; preorder(root, res); return res; } /*this function deserializes the serialized vector A*/ int dserial = 0; Node* deSerialize(vector &A){ if(dserial == A.size() || A[dserial] == -1){ dserial++; return nullptr; } Node *root; root->data = A[dserial]; dserial++; root->left = deSerialize(A); root->right = deSerialize(A); return root; }

[@tonyriddle7646]

never mind ...found the error this should be the statement... Node *root = new Node(A[dserial]); I didnt know i can do that with struct too...

[@ZiiiP2142]

Awesome

[@IDeserve]

Thanks Ádám for your kind words :) We would really appreciate if you could spread the word about IDeserve in your college and to your colleagues. Also please check out our website at: www.ideserve.co.in It has features like Algorithm Visualization, Learn Together and many more coming soon. Please check it out and leave us a comment there! Thanks, -Team IDeserve.

[@chanakyaveer8257]

GOODGOOD