🌲 Tree Playlist: kzread.info/dash/bejne/gaKH0JSRdbSafbw.html

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

@NeetCode

3 жыл бұрын

Thanks, I'm happy theyre helpful :)

@tonyz2203

2 жыл бұрын

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

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

2 жыл бұрын

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

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.

Great explanation and straightforward solution!

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.

i should've went to art school

@yang5843

2 жыл бұрын

in Austria?

@dittocopys

2 жыл бұрын

@@yang5843 not in Austria

@antonw8134

2 жыл бұрын

m.kzread.info/dash/bejne/YqJoyI-PdM21cqg.html

@PippyPappyPatterson

2 жыл бұрын

@@dittocopys Where is Not-In-Austria?

@prasadm3614

8 ай бұрын

Lol.... I'm with you

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

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.

Awesome explanation. Please do Q&A sessions.

Your channel is awesome.

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

9 ай бұрын

or you can use nonlocal i in your inner function

thanks for such simple solutions,

Thank you!

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.

U a God

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

2 жыл бұрын

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

2 жыл бұрын

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.

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

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

@DmitriyKl

8 ай бұрын

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?

Thank you so much.... 😭😭😭

Great video just to be specific this is bottom up DFS

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.

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

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

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

2 жыл бұрын

Can you provide a specific test case?

@douglaswong6560

2 жыл бұрын

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

Can we do this using just inorder traversal for serialization?

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

2 жыл бұрын

Correct, we just use i += 1.

@harshtiku3240

2 жыл бұрын

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

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

@dineshbhaskar8561

11 ай бұрын

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.

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

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

23 күн бұрын

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

damn it. failed final interview because of this question.

@leonscander1431

10 күн бұрын

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

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)

WORD BREAK - solve if possible

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

@eddieh5036

2 жыл бұрын

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

2 жыл бұрын

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

why do you use recursive functions in python.

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

@kryddan

5 ай бұрын

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.

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

Do it in c++ without recursion...

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?

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

2 жыл бұрын

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

5 ай бұрын

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

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

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] kzread.info/dash/bejne/moiBldKhhqycibQ.html

@minciNashu

2 жыл бұрын

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

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

@kryddan

5 ай бұрын

"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.

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

@dorondavid4698

2 жыл бұрын

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

@ChrisCox-wv7oo

2 жыл бұрын

@@dorondavid4698 still showing as Hard for me

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