Serialize and Deserialize Binary Tree - Preorder Traversal - Leetcode 297 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/serializ...
0:00 - Read the problem
1:32 - Drawing Explanation
8:20 - Coding Explanation
leetcode 297
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#preorder #traversal #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@NeetCode]

🌲 Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@tanayshah275]

Awesome Explanation! posting code for deserializing without using global variables, just in case anyone wants to take a look def deserialize(self, data): nodes = data.split(',') def dfs(i): if nodes[i] == 'N': return (None, i + 1) node = TreeNode(int(nodes[i])) i += 1 node.left, i = dfs(i) node.right, i = dfs(i) return (node, i) return dfs(0)[0]

[@linchuantian623]

hi I have a question so if a tree looks like tree= [2 , 3 ,4] so the 2.left=tree[i+1] and 2.right=tree[i+2] right? I am very confused by he said that because it is recursion we only need to do addition 1 time

[@ahyeoncho7685]

I really appreciate these videos. Thank you. I watch at least 10 a day.

[@NeetCode]

Thanks, I'm happy theyre helpful :)

[@tonyz2203]

that's too fast

[@fefefefefee32]

@@tonyz2203 Lol, everyone has their pace of learning. I do 10 too.

[@yakeensabha655]

I've watched this vid more than 10 times today and still don't get it 😢. I think I might be not smart enough.

[@user-qlksojfieopanj]

@@yakeensabha655you got this

[@ayusharora9502]

Have always learned to serialize (aka turn into a array of some traversal) but never learned how to deserialize, learned something new! thank you very much

[@ax5344]

Awesome. Please keep posting these high frequency interview questions. There is another 99 in Tree, but it"s in the hard difficulty.

[@DavidDLee]

If you don't fall for using in-order traversal, this is quite easy. The only "hard" thing was to write a function to compare trees, if you don't get it from a platform already. Otherwise, it's hard to know if it worked / is correct. In-order traversal DFS will not work, because it will print the smallest (deepest / left-most) nodes first, and even then, it will start with null. Now, the null is ambiguous on decode, unless you do something extra, such as encoding depth or node start.

[@farshadsaberi2740]

Great explanation and straightforward solution!

[@BostonzPROPHET]

Thanks for the explanation! I was close with the serialization except I was using a string and adding in the commas instead of using the ",".join method on an array. I was also pretty stuck on the deserialization since I had not added the "N". This video was very helpful.

[@DesktopDev_mfaisaltariq]

For deserialization you can use the Iteratable object with Next in python instead of using a global variable def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data: return None nodes = iter(data.split(',')) return self.buildTree(nodes) def buildTree(self,nodes): val = next(nodes) if val == 'none': return node = TreeNode(str(val)) node.left = self.buildTree(nodes) node.right = self.buildTree(nodes) return node

[@markolainovic]

Nice!

[@amberfatima2777]

or you can use nonlocal i in your inner function

[@matthewtang1490]

As soon as I get to the LC Hard problems, you already have a video posted for it :)

[@sauravdeb8236]

Awesome explanation. Please do Q&A sessions.

[@dittocopys]

i should've went to art school

[@yang5843]

in Austria?

[@dittocopys]

@@yang5843 not in Austria

[@antonw8134]

m.kzbin.info/www/bejne/Zp-Xl2CMec-CeKc

[@PippyPappyPatterson]

@@dittocopys Where is Not-In-Austria?

[@prasadm3614]

Lol.... I'm with you

[@bryand7958]

Your channel is awesome.

[@---el6pq]

Java solution using BFS: public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) return ""; StringBuilder res = new StringBuilder(); Deque dfs = new LinkedList(); int size = 1; dfs.addFirst(root); TreeNode temp = root; while (size > 0) { for (int i = 0; i < size; i++) { temp = dfs.pollLast(); if (temp == null) res.append(",null"); else { res.append("," + temp.val); dfs.addFirst(temp.left); dfs.addFirst(temp.right); } } size = dfs.size(); } res.deleteCharAt(0); return res.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.equals("")) return null; List nodes = new ArrayList(Arrays.asList(data.split(","))); while (nodes.get(nodes.size() - 1).equals("null")) nodes.remove(nodes.size() - 1); int fast = 1; Deque dfs = new LinkedList(); TreeNode head = new TreeNode(Integer.valueOf(nodes.get(0))); TreeNode temp = head; dfs.addFirst(head); int size = 1; while (size > 0) { for (int i = 0; i < size; i++) { temp = dfs.pollLast(); if (temp == null) continue; if (fast >= nodes.size()) break; if (!nodes.get(fast).equals("null")) temp.left = new TreeNode(Integer.valueOf(nodes.get(fast))); fast++; if (fast >= nodes.size()) break; if (!nodes.get(fast).equals("null")) temp.right = new TreeNode(Integer.valueOf(nodes.get(fast))); fast++; dfs.addFirst(temp.left); dfs.addFirst(temp.right); } size = dfs.size(); } return head; } }

[@AmolGautam]

thanks for such simple solutions,

[@Sookuto]

Thank you!

[@techwills4619]

Another approach : {binary tree}--------(leetcode 94 and 144) ----->{preorder, inorder} --------(leetcode 105)------> (binary tree}

[@DmitriyKl]

This is what I came up with too! Like @kevinburgerking1591 said, the solution won't work "as is" because of duplicate values. My solution was to make each value unique by appending some arbitrary character (like "@") to every value, append "L" or "R", and append the level of the node. In that case elements in the encoded string will look like "4@L15" - element with value 4 in the left subtree on the 15th level. It's a very hacky solution, but I really wanted to make it work since I realized the caveat of unique values way too late

[@VasudevaK]

@@DmitriyKl Why do you think it wouldn't work with duplicate values?

[@DJ-wo9nd]

How does it know to switch to nodes.right in the deserialize methodto get the correct right node value? I can visualize recursion through the tree for nodes.left and nodes.right but this is setting it.

[@edwardteach2]

U a God

[@mayukhnath1017]

Great explanation. I have a question: Why don't we have to declare res=[ ] as a global variable(self.res=[ ] ) like we are declaring self.i ?

[@zhaozheng7704]

Int is immutable. When you try to change the value of "i" inside the nested function, a new integer object is created, and the local variable is rebound to the new object. When returning from the function, that's lost, and the value of "i" remain unchanged. In contrast, list is mutable.

[@dollyvishwakarma2]

Basically lists are mutable, so when you pass a list to a function, whatever changes the function does to the list are reflected in the original list --> in a way the list behaves as a global variable but the same is not true for a variable (integer i here in this solution). Once you perform any assignment operation on a variable inside the function, that variable is treated as a local variable, thus it is important to declare the variable as global explicitly.

[@rsKayiira]

Great video just to be specific this is bottom up DFS

[@dorondavid4698]

Quick question; does python not have a post incrementor (i++)? Or you just like doing i += 1? I've seen you do this in other vids so was just wondering

[@Lambyyy]

Correct, we just use i += 1.

[@harshtiku3240]

python does not have a post incrementor. i+=1 or i = i+1 are the only two choices

[@shwethaks7994]

Boundary of Binary Tree please can you make a video of it.

[@samrey8134]

Thank you so much.... 😭😭😭

[@EduarteBDO]

For the deserialize I reversed the list then popped the last element instead of using an index: data = data.split(',') data.reverse() def createTree(lista:list) -> TreeNode: value = lista.pop() if value == 'N':return None node = TreeNode(value) node.left = createTree(lista) node.right = createTree(lista) return node return createTree(data)

[@abyxatjov4018]

Since everyone is sharing their solution, heres mine: def serialize(root): return '-' if root is None else ' '.join([root.val, serialize(root.left), serialize(root.right)]) def deserialize_rec(s): def deserialize_aux(tree): temp = tree.popleft() if temp == '-': return None n = Node(temp) n.left = deserialize_aux(tree) n.right = deserialize_aux(tree) return n return deserialize_aux(deque(s.split(' ')))

[@akshayiithyd]

I recently tried to serialize using BFS, but I am getting a Memory Limit Exceeded error the second last test case(which is almost a linked list). Has anyone done this with BFS?

[@chaitanyayeole4111]

Can we do this using just inorder traversal for serialization?

[@monicawang8447]

Heyy I have a question: for the tree deserialization part, why wouldn't it run into error of exceeding boundary as we keep incrementing self.i? Which part prevents this issue? Thanks!

[@yang5843]

Can you provide a specific test case?

[@douglaswong6560]

self.i is bounded by res[self.i] == "N"

[@ajinkyap4246]

Because the last 2 values in the array will always be null / N so both will be popped out and won't call left and right on that.

[@Babe_Chinwendum]

I have the same confusion

[@hwang1607]

what is the difference between using a variable with self. vs using a nonlocal variable

[@dineshbhaskar8561]

Nonlocal is used within a nested function and is used to access a non-local or a variable that is not defined in it's own body, but is defined in the body of the enclosing function. In other words it can be understood as going one level up and fetching a variable for local use. Whereas for self.i it is in the global scope and any function(method) can access this variable at any scope in the same module.

[@chaitanyayeole4111]

Deserialization without using Global Variable def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ serialized_values = iter(data.split(",")) def dfs(): values = next(serialized_values) if values == "N": return None node = TreeNode(int(values)) node.left = dfs() node.right = dfs() return node return dfs()

[@robertlemiesz7143]

why do you use recursive functions in python.

[@jonaskhanwald566]

WORD BREAK - solve if possible

[@vibhumrajtripathi4276]

But don't we need both preorder and inorder traversal to construct a tree.??

[@eddieh5036]

I think for binary "search" tree you only need one since the order is fixed. Please let me know if my understanding is wrong.

[@vibhumrajtripathi4276]

@@eddieh5036 yes, it's correct because we know the inorder traversal of search tree, just the sorted array.

[@harishkp8631]

why cant we create find inorder and preorder traversal and create a binary tree from that

[@kryddan]

Because the values of the nodes are not guaranteed to be unique, unlike the similar LC question which lets you construct a tree from pre + post-order traversal, but it has that unique constraint.

[@smtp_yurzx]

I asked chat gpt it's solution. It wrote a breadth-first search solution first then returned a depth first search solution identical to yours

[@Tristan87688]

Do it in c++ without recursion...

[@1murkeybadmayn]

Pardon me, I'm a beginner coder. So 1:16 the output says it should be [1,2,3,N,N,4,5] but you don't explain why at 4:59 you are having the output be [1,2,N,N,3,4,N,N,5,N,N]. The former looks like level order traversal, which nobody seems to mention, but the latter is clearly preorder traversal so won't that change the output array from what the question asks?

[@danielderese3170]

damn it. failed final interview because of this question.

[@albertjtyeh53]

Hmm id say this is the first video of of 15 or so that was unclear to me. The logic of deserialize just didnt click. I dont understand by in incrementing i that we know that the next in line is the left and then right everytime. Please expound if possible. Thanks though.

[@yimengwang7865]

Because that is the pattern, in serializing, we added the left first then right, similarly, when we deserialize, we are going to add left first then right

[@thndesmondsaid]

right and to add to what @yimengwang7865 said, you deserialize the string from left to right.

[@Akaash449]

original question had "null" for denoting Null, while you used "N" for denoting null in your code. How did it not throw error ??

[@kryddan]

"N" is never added as a node in the actual tree representation. The TreeNode() class has a default value of left and right. = None, so if you don't assign them they will be None implicitly.

[@PippyPappyPatterson]

I wonder why you used a counter `i` instead of a `deque` like in your Iterative DFS Solution to Max Depth Binary Tree [1]. If anyone has any thoughts on the advantages or disadvantages of using a counter vs a double-ended queue I'd love to hear them. [1] kzbin.info/www/bejne/noWwZKOei65pj7M

[@minciNashu]

you don't need a deque. you can simulate a deque with an interator applied to the list def deserialize(self, data: str) -> TreeNode: def dfs(vals) -> TreeNode: val = next(vals) if val != '#': node = TreeNode(int(val)) node.left = dfs(vals) node.right = dfs(vals) return node return None return dfs(iter(data.split(',')))

[@sreejith5966]

I think it should be a medium level question have seen a lot of medium questions harder than this

[@dorondavid4698]

You got your wish...On Leetcode it's now Medium :D

[@ChrisCox-wv7oo]

@@dorondavid4698 still showing as Hard for me

[@GAHbl4]

converted to java public class Codec { List list = new ArrayList(); // Encodes a tree to a single string. public String serialize(TreeNode root) { dfsSer(root); return String.join(",",list); } void dfsSer(TreeNode root){ if(root == null) { list.add("N"); return; } list.add(String.valueOf(root.val)); dfsSer(root.left); dfsSer(root.right); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String[] desData = data.split(","); return dfsDes(desData); } int i = 0; TreeNode dfsDes(String[] data){ if(data[i].equals("N")){ i++; return null; }else{ TreeNode node = new TreeNode(Integer.parseInt(data[i])); i++; node.left = dfsDes(data); node.right = dfsDes(data); return node; } } }