You make complicated problems appear so simple and make us guilty on why we could not think of that solution!! Great explanation and code as usual! Thank you!!
I was struggling so hard, because out of all the videos I watched for this question, everyone seemed to use a very vague recursive logic without much intuition of the logic behind it. The way you told to write the recursive calls, the way you handled edge cases, I was able to understand it so clearly, that I was able to code your solution without seeing, as well as modify my own code which gave wrong answer while submitting three times, to work correctly for the fourth time!!! Thank you so very much :)
Keeping track of the order while recursing seemed difficult to me, so I solved it using a deque instead, using the intuition that preorder traversal is essentially popping from the left and appending potential child nodes back to the left of the deque: class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ q = deque() q.append(root) q.append(None) while q[0] is not None: node = q.popleft() if node.right: q.appendleft(node.right) if node.left: q.appendleft(node.left)
very simple and easy to understand, i usually search for simple ways so I do not forget the approach to the solution and the video was making it a bit complicated, thanks for this solution
I just did this the other day [Wanted to try one that wasn't on your playlist yet] ! Man you are fast though, it took me 15 minutes to even come up with the appropriate strategy. Keep it up. My favorite channel
Excellent explanation! I have a follow up question on this. Given the flattened LinkedList as arrived in this solution, can we traverse this flattened LinkedList and reconstruct the original Binary Tree? Thanks
Follow up: Can you flatten the tree in-place (with O(1) extra space)? I saw that follow up. If I use O(1) extra space then I have to move the right subtree under the right most position of the left subtree to avoid extra O(h) storage. But if I do that, the running time would be O(nlog(n)). Anyone has any better ideas?
A somewhat different solution: def flatten(self, root: Optional[TreeNode]) -> None: if root: # We keep track of the pointers to the left and the right subtrees left = root.left right = root.right # We cut the link between the root and the left and right subtrees for independance root.left = None root.right = None # We flatten each subtree self.flatten(left) self.flatten(right) # We reattach the first part to the root, meaning the left part since it is a pre-order thingy root.right = left # We also need to reattach the flattened right subtree to the end of left subtree prev, current = root, left while current is not None: prev = current current = current.right prev.right = right
Brute force is almost same complexity. DFS and add node pointer to list. Then iterate list and point list[n].right = list[n+1] and list[n].left = NULL. O(n) time and space. Simple af.
I have a few questions: 1) when doing the swapping: I thought of something like this root.left= None leftTail.right = rightTail root.right = leftTail. Why are we using the root and not the tails.
Because at each node we simply get a tail value from left branch. The tail value order is (rightTail, leftTail or root). At root (1) leftTail is (4) rightTail is (6) leftTail.right = root.right 4 -> 5 root.right = root.left 1 -> 2 root.left = None 1 / \ NULL 2 \ 4 \ 5 Try solving it on paper and you'll see it :)
keep going , everyday i wait for you to post a video and go try it before returning to watch your explanation, and sometimes my solution looks the same like yours : def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.dfs(root) def dfs(self, root): if not root: return
if not (root.left or root.right): print(root.val) return root
Great explanation: Here i tried this question by traversing the right most subtree first -- I found it a little more easier to understand. ``` class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.temp = None def helper(root): if not root: return helper(root.right) helper(root.left) root.right = self.temp root.left = None self.temp = root helper(root) ```
Share to you another solution that may be easier to understand: processing from the "bottom-right" to the "top-left" in the flattened tree class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ prev = None def helper(current): # process right-left-root order, i.e: processing from the back (button-right to top-left) # so, the previously processed node (prev) is actually the "right node" of "current node" nonlocal prev if current is None:# basis return else: helper(current.right) helper(current.left) current.right = prev current.left = None prev = current helper(root)
Your code is returning the pointer to Node: 6 if we take the example given in the question. Shouldn't it return the pointer to Node: 1. In short why are we returning the pointer to the tail?
U a God. I had a different condition in the if root.left condition. The code in the video doesn't work anymore. class Solution(object): def flatten(self, root): """ :type root: TreeNode :rtype: None Do not return anything, modify root in-place instead. """ def dfs(root): if not root: return root left_node = dfs(root.left) right_node = dfs(root.right) if root.left: root.left = None root.right = left_node while left_node.right: left_node = left_node.right left_node.right = right_node return root dfs(root)
For the sudoku solver just use 3 hashsets (One for the row, one for the column, one for the section of the board). The tricky part is for the section is a math equation to turn row and column number to section number (think section=m*row + column). Traverse the game board and check that no duplicates are in your hashsets. Time O(m*n), Space Complexity O(m*n) where m = number of rows, n=number of columns
""" 1 / \ 2 5 / \ \ 3 4 6 Step 1: Flatten the left subtree of 1 Call: dfs(1) Call: dfs(2) Call: dfs(3) root.left and root.right are None Return 3 (last node in the left subtree of 2) Call: dfs(4) root.left and root.right are None Return 4 (last node in the right subtree of 2) leftTail = 3, rightTail = 4 Set 3.right = 4 Set 2.right = 3, 2.left = None Return 4 (last node in the flattened subtree of 2) Step 2: Flatten the right subtree of 1 Call: dfs(5) Call: dfs(None) Return None Call: dfs(6) root.left and root.right are None Return 6 (last node in the right subtree of 5) leftTail = None, rightTail = 6 Return 6 (last node in the flattened subtree of 5) Step 3: Combine left and right subtrees of 1 leftTail = 4, rightTail = 6 Set 4.right = 5 Set 1.right = 2, 1.left = None Return 6 (last node in the flattened tree) """
🌲 TREE PLAYLIST: ruclips.net/video/OnSn2XEQ4MY/видео.html
You make complicated problems appear so simple and make us guilty on why we could not think of that solution!! Great explanation and code as usual! Thank you!!
Unbelievable sir. How are you still solving these problems.
@@jonaskhanwald566 Heyy how is martha???
I was struggling so hard, because out of all the videos I watched for this question, everyone seemed to use a very vague recursive logic without much intuition of the logic behind it. The way you told to write the recursive calls, the way you handled edge cases, I was able to understand it so clearly, that I was able to code your solution without seeing, as well as modify my own code which gave wrong answer while submitting three times, to work correctly for the fourth time!!! Thank you so very much :)
One of the best programming channels on RUclips.. Hands down please keep doing this
Blessed are we to have such a channel, for helping us. Please do keep doing the amazing work!!
Thanks! What about "Follow up: Can you flatten the tree in-place (with O(1) extra space)?"
The solution in this video uses O(1) memory, so the answer is "yes"
@@spikygoldfish it's not O(1) memory because it uses recursion
@@spikygoldfishit takes O(n) space in the worst case (let's say a skewed tree).
Keeping track of the order while recursing seemed difficult to me, so I solved it using a deque instead, using the intuition that preorder traversal is essentially popping from the left and appending potential child nodes back to the left of the deque:
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
q = deque()
q.append(root)
q.append(None)
while q[0] is not None:
node = q.popleft()
if node.right:
q.appendleft(node.right)
if node.left:
q.appendleft(node.left)
node.left = None
node.right = q[0]
return root
very simple and easy to understand, i usually search for simple ways so I do not forget the approach to the solution and the video was making it a bit complicated, thanks for this solution
Timestamp 13:05 - 13:06: Discord notification alert. :)
I just did this the other day [Wanted to try one that wasn't on your playlist yet] ! Man you are fast though, it took me 15 minutes to even come up with the appropriate strategy. Keep it up. My favorite channel
best channel, anytime I need good explanation, NeetCode is very helpful
"Return rightTail or leftTail or root" is too hard to understand. It's not simply like the question wants us to return the tail.
Excellent explanation!
I have a follow up question on this.
Given the flattened LinkedList as arrived in this solution, can we traverse this flattened LinkedList and reconstruct the original Binary Tree? Thanks
Follow up: Can you flatten the tree in-place (with O(1) extra space)? I saw that follow up. If I use O(1) extra space then I have to move the right subtree under the right most position of the left subtree to avoid extra O(h) storage. But if I do that, the running time would be O(nlog(n)). Anyone has any better ideas?
+1 the follow up is confusing :(
This was tough for me to solve on my own. It makes so much sense now thank you!
Best tutorials on youtube by far !!!!
A somewhat different solution:
def flatten(self, root: Optional[TreeNode]) -> None:
if root:
# We keep track of the pointers to the left and the right subtrees
left = root.left
right = root.right
# We cut the link between the root and the left and right subtrees for independance
root.left = None
root.right = None
# We flatten each subtree
self.flatten(left)
self.flatten(right)
# We reattach the first part to the root, meaning the left part since it is a pre-order thingy
root.right = left
# We also need to reattach the flattened right subtree to the end of left subtree
prev, current = root, left
while current is not None:
prev = current
current = current.right
prev.right = right
Isn't it O(n*h) solution 🤔
@@light2929 nope
This is very clever, thanks
Brute force is almost same complexity. DFS and add node pointer to list. Then iterate list and point list[n].right = list[n+1] and list[n].left = NULL. O(n) time and space. Simple af.
I am your big fan, but please make more videos on dynamic programming as it's one of the most confusing topic. Thanks.
what are the values that returned from leftTrail=dfs(root.left) and rightTrial=dfs(root.right)?
I have a few questions:
1) when doing the swapping:
I thought of something like this
root.left= None
leftTail.right = rightTail
root.right = leftTail.
Why are we using the root and not the tails.
Because at each node we simply get a tail value from left branch.
The tail value order is (rightTail, leftTail or root).
At root (1)
leftTail is (4)
rightTail is (6)
leftTail.right = root.right
4 -> 5
root.right = root.left
1 -> 2
root.left = None
1
/ \
NULL 2
\
4
\
5
Try solving it on paper and you'll see it :)
leftTail.right = rightTail is wrong. rightTail is just a single node. root.right is the sub tree. root,right is a tree, rightTail is a node
but this is not constant space right? The implementation of the recursion is implicit stack which would be O(n)
keep going , everyday i wait for you to post a video and go try it before returning to watch your explanation, and sometimes my solution looks the same like yours :
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.dfs(root)
def dfs(self, root):
if not root:
return
if not (root.left or root.right):
print(root.val)
return root
r, l = self.dfs(root.right), self.dfs(root.left)
if root.left:
l.right = root.right
root.right = root.left
root.left = None
last = r if r else l
return last
Great explanation:
Here i tried this question by traversing the right most subtree first -- I found it a little more easier to understand.
```
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.temp = None
def helper(root):
if not root:
return
helper(root.right)
helper(root.left)
root.right = self.temp
root.left = None
self.temp = root
helper(root)
```
Share to you another solution that may be easier to understand: processing from the "bottom-right" to the "top-left" in the flattened tree
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
prev = None
def helper(current):
# process right-left-root order, i.e: processing from the back (button-right to top-left)
# so, the previously processed node (prev) is actually the "right node" of "current node"
nonlocal prev
if current is None:# basis
return
else:
helper(current.right)
helper(current.left)
current.right = prev
current.left = None
prev = current
helper(root)
Why we have to return the list tail?
Thanks!
Gareeb
To solve in O(1) space you would have to do Morris traversal, allegedly. I don't think any of us are busting that out in an interview, though
Thank you all your videos are very usefull
Very clear explanation. Thank you :)
Thank you very much man
Your code is returning the pointer to Node: 6 if we take the example given in the question. Shouldn't it return the pointer to Node: 1. In short why are we returning the pointer to the tail?
did anyone else hear a discord sound?
But isn't it post order traversal?
Very helpful, thank you!
This question is one of those that after watching the video 3 times, I'm still confused
no need for a helper function, can just write the same logic inside flatten :)
he said that the only reason for helper was that the flatten func is hinted to return None
U a God. I had a different condition in the if root.left condition. The code in the video doesn't work anymore.
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
def dfs(root):
if not root:
return root
left_node = dfs(root.left)
right_node = dfs(root.right)
if root.left:
root.left = None
root.right = left_node
while left_node.right:
left_node = left_node.right
left_node.right = right_node
return root
dfs(root)
Does this work?
You're right, thanks for the updated solution, it works
please make video of sudoku solver
For the sudoku solver just use 3 hashsets (One for the row, one for the column, one for the section of the board). The tricky part is for the section is a math equation to turn row and column number to section number (think section=m*row + column). Traverse the game board and check that no duplicates are in your hashsets. Time O(m*n), Space Complexity O(m*n) where m = number of rows, n=number of columns
Problem before seeing Neetcode: Wth is this?!
Problem after seeing Neetcode: Oh. Such a simple problem!
what's "next" attribute? we do not have such in the TreeNode class
watch it again!
Beautiful
Love you
could oyu explain it again
is neetcode real ?
discord msg
Explanation was BULLSHIT
"""
1
/ \
2 5
/ \ \
3 4 6
Step 1: Flatten the left subtree of 1
Call: dfs(1)
Call: dfs(2)
Call: dfs(3)
root.left and root.right are None
Return 3 (last node in the left subtree of 2)
Call: dfs(4)
root.left and root.right are None
Return 4 (last node in the right subtree of 2)
leftTail = 3, rightTail = 4
Set 3.right = 4
Set 2.right = 3, 2.left = None
Return 4 (last node in the flattened subtree of 2)
Step 2: Flatten the right subtree of 1
Call: dfs(5)
Call: dfs(None)
Return None
Call: dfs(6)
root.left and root.right are None
Return 6 (last node in the right subtree of 5)
leftTail = None, rightTail = 6
Return 6 (last node in the flattened subtree of 5)
Step 3: Combine left and right subtrees of 1
leftTail = 4, rightTail = 6
Set 4.right = 5
Set 1.right = 2, 1.left = None
Return 6 (last node in the flattened tree)
"""
Thanks!