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

🌲 Tree Playlist: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-OnSn2XEQ4MY.html

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]

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

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

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

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.

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.

Great explanation and straightforward solution!

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

Awesome explanation. Please do Q&A sessions.

i should've went to art school

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

Your channel is awesome.

thanks for such simple solutions,

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.

Thank you!

U a God

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

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 ?

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

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

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!

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.

Great video just to be specific this is bottom up DFS

Thank you so much.... 😭😭😭

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

Can we do this using just inorder traversal for serialization?

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?

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

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

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

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

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)

damn it. failed final interview because of this question.

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?

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

WORD BREAK - solve if possible

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

why do you use recursive functions in python.

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

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

Do it in c++ without recursion...

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.

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] ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-hTM3phVI6YQ.html

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

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

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