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

[@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

[@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.

[@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

[@ddshoo5282]

level order / bfs: # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Codec: #Encodes a tree to a single string. def serialize(self, root: TreeNode) -> str: if not root: return "" q = deque() q.append(root) res = [] res.append(str(root.val)) while q: cur = q.popleft() if cur.left: q.append(cur.left) res.append(str(cur.left.val)) else: res.append("N") if cur.right: q.append(cur.right) res.append(str(cur.right.val)) else: res.append("N") return ",".join(res) # Decodes your encoded data to tree. def deserialize(self, data: str) -> TreeNode: if not data: return None data = data.split(",") q = deque() root = TreeNode(data[0]) q.append(root) i = 1 while q: cur = q.popleft() if data[i] != "N": left = TreeNode(data[i]) cur.left = left q.append(left) i += 1 if data[i] != "N": right = TreeNode(data[i]) cur.right = right q.append(right) i += 1 return root

[@learnsleeplearn]

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

[@draugno7]

i didn't remember to just write nulls in encoded string, so I put len#level(l/r)nodeval so it got overly complicated... this is amazingly simple!

[@ax5344]

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

[@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.

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

[@xkcd_68868]

@@VasudevaK Because for building tree back from pre and inorder, there is an index fetch part. The index fetch fails to grab the right index for inorder list. I also came up with pre+in order solution, although it passed all neetcode tests, it failed leetcode tests.

[@matthewtang1490]

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

[@---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; } }

[@princedesnare4373]

boilerplate be real

[@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

[@sauravdeb8236]

Awesome explanation. Please do Q&A sessions.

[@tanishgotti3659]

Preorder is enough to reconstruct a unique binary tree if it also includes null markers to preserve structure.

[@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()

[@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(' ')))

[@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.

[@farshadsaberi2740]

Great explanation and straightforward solution!

[@omerabbas2346]

The data could have a comma in and of itself causing split and join to not necessarily be invertible. That's where the difficultly comes from

[@leonscander1431]

I thought it was impossible to solve it only with preorder traversal, because of the previous problem where we were given 2 traversals (preorder and inorder) to build tree from. That confused me so I gave up. The only idea I implemented was converting tree to a json string.

[@chaitanyayeole4111]

Can we do this using just inorder traversal for serialization?

[@AmolGautam]

thanks for such simple solutions,

[@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

[@lukelyu3264]

Wondering why the tree build-up is kinda off when running the deserialize function separately: class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Codec: def deserialize(self): vals = ['1','2','3','N','N', '4','5'] self.i = 0 def dfs(): if vals[self.i] == "N": self.i += 1 return None node = TreeNode(int(vals[self.i])) self.i += 1 node.left = dfs() node.right = dfs() return node return dfs() run = Codec() run.deserialize()

[@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.

[@rsKayiira]

Great video just to be specific this is bottom up DFS

[@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)

[@bryand7958]

Your channel is awesome.

[@robertlemiesz7143]

why do you use recursive functions in python.

[@Sookuto]

Thank you!

[@shwethaks7994]

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

[@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.

[@tanishgotti3659]

Preorder is enough to reconstruct a unique binary tree if it also includes null markers to preserve structure.

[@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

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

[@ddshoo5282]

yeah, that was my first thought since the example was level order # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Codec: #Encodes a tree to a single string. def serialize(self, root: TreeNode) -> str: if not root: return "" q = deque() q.append(root) res = [] res.append(str(root.val)) while q: cur = q.popleft() if cur.left: q.append(cur.left) res.append(str(cur.left.val)) else: res.append("N") if cur.right: q.append(cur.right) res.append(str(cur.right.val)) else: res.append("N") return ",".join(res) # Decodes your encoded data to tree. def deserialize(self, data: str) -> TreeNode: if not data: return None data = data.split(",") q = deque() root = TreeNode(data[0]) q.append(root) i = 1 while q: cur = q.popleft() if data[i] != "N": left = TreeNode(data[i]) cur.left = left q.append(left) i += 1 if data[i] != "N": right = TreeNode(data[i]) cur.right = right q.append(right) i += 1 return root

[@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

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

[@jonaskhanwald566]

WORD BREAK - solve if possible

[@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.

[@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.

[@Tristan87688]

Do it in c++ without recursion...

[@samrey8134]

Thank you so much.... 😭😭😭

[@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

[@danielderese3170]

damn it. failed final interview because of this question.

[@leonscander1431]

Didn't you came up with any solution or they wanted you to optimize your solution?

[@ghadeeralabandi2523]

@@leonscander1431 I got the question for first interview and got rejected even though I was able to solve it but I think interviewer didn't like my solution of using BFS instead of DFS.

[@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(',')))

[@burburchacha]

this isn't a "hard" problem, should be re-labeled as "medium"

[@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; } } }