On the line level = reversed(level) if len(res) % 2 else level you're actually appending a reverse iterator because that's what reversed() returns. You can see this if you print out `res`. You should actually call list(reversed(level)). LeetCode converts it to a list while checking your answer so it works on LeetCode. But it won't work in general. Anyway, probably a simpler way is to just reverse the level in-place. It's also more efficient. if len(res) % 2: level.reverse()
In fact when I decided to traverse every odd level in reverse order not only it was more complex it's actually not even correct eg: [1,2,3,4,null,null,5] expected : [[1] , [3,2] , [4,5]] output: [[[1] , [3,2] , [5,4]]
Great video as always. One question, are you going to link all these videos to your Neetcode All section of your website? It really helps me with keeping track of all the problems by category (Hashmaps, Binary Trees, Graphs, etc.) Thanks again for the content!
we can do it as an audience if u want. like have a public spreadsheet and do it/maintain it for him. or ill make a website with a list and ill categorize them for everyone. could be fun. if neetcode or any of u want a solution like that, just let me know. neetcode is already doing so much for free. thanks for the daily.
Hi neetcode! I'm pretty proud I did this one, although I didn't use the way that was intended to be the solution. ans = [] def dfs(node, h): if not node: return while h >= len(ans): ans.append([]) ans[h].append(node.val) dfs(node.left, h + 1) dfs(node.right, h + 1) dfs(root, 0) for i in range(len(ans)): if i % 2: ans[i].reverse()
return ans Tell me what you think. Dfs is alot easier for me to implement so I always slant towards it.
For each reverse, it only reverse the number of items in that level. If you look at how many total items are being reversed, it’s roughly half of them, so O(n/2) which can simplify to O(n). So really, we’re just doing O(n) extra work so O(n)+O(n)=O(2n) = O(n).
Think about it more in terms of filling the array, which is O(n), and then performing a reversal on the entire array on after filling it. This is still O(n).
Shouldn't the time complexity be O(n^2) since half of the height of the tree your are reversing the level. It the tree is a perfect binary tree the last level is size n/2 which effectively is n. If we are reversing the nodes of each level that is odd, then at worst we get closer to O(n^2). This is my conclusion, not sure why we shouldn't take into consideration the reversal part.
A totally useless optimization we can make to not have to reverse odd indexed arrays, is to use the double sided constant time addition/deletion property thing of a deque. Basically, if we are going from left -> right i.e. popping from beginning of the deque, we add the children to the end (left child first then right), else if we are going from right -> left i.e. popping from the end of the deque, we add the children to the start(right child first then left) This way we do a zig-zag bfs which kinda feels nauseating to imagine while dry running That way we visit each node only once, so atmost ~n operations, O(n) TC.
thank you for uploading the daily problems! much appreciated
Thanks for immediately uploaded solution! I decided not to reverse each second list, and used stack instead. As a result got 86% by time.
Nice clean and fast solution!
On the line
level = reversed(level) if len(res) % 2 else level
you're actually appending a reverse iterator because that's what reversed() returns. You can see this if you print out `res`. You should actually call list(reversed(level)).
LeetCode converts it to a list while checking your answer so it works on LeetCode. But it won't work in general.
Anyway, probably a simpler way is to just reverse the level in-place. It's also more efficient.
if len(res) % 2:
level.reverse()
Thank you for another great explanation sir !
In fact when I decided to traverse every odd level in reverse order not only it was more complex it's actually not even correct
eg: [1,2,3,4,null,null,5]
expected : [[1] , [3,2] , [4,5]]
output: [[[1] , [3,2] , [5,4]]
Just Awesome!!!
Thank you so much
Nice explanation . Could you please post the videos for the leetcode problem no 979 and 2266 ? They are interesting as well as tricky.
Thanks!
Thank you
Leetcode102 Would be also cool to see in your explanation :)
Great video as always. One question, are you going to link all these videos to your Neetcode All section of your website? It really helps me with keeping track of all the problems by category (Hashmaps, Binary Trees, Graphs, etc.) Thanks again for the content!
we can do it as an audience if u want. like have a public spreadsheet and do it/maintain it for him. or ill make a website with a list and ill categorize them for everyone. could be fun. if neetcode or any of u want a solution like that, just let me know.
neetcode is already doing so much for free. thanks for the daily.
@@uptwist2260 cool idea to make a website mate! Let me know if you're making the website, I'll contribute!!
Hi neetcode! I'm pretty proud I did this one, although I didn't use the way that was intended to be the solution.
ans = []
def dfs(node, h):
if not node: return
while h >= len(ans): ans.append([])
ans[h].append(node.val)
dfs(node.left, h + 1)
dfs(node.right, h + 1)
dfs(root, 0)
for i in range(len(ans)):
if i % 2: ans[i].reverse()
return ans
Tell me what you think. Dfs is alot easier for me to implement so I always slant towards it.
Nice soln keep it up !
@@saifahmad141 Thank you!
I tried using the logic of BFS traversal and for every alternate level I popped either from the right or the left but I got time limit exceeded error.
my bad I used a list in the wrong for loop XD
why not just swap the order of adding node.right and node.left depending on which level we are on for reduced space complexity
Reverse in itself is O(N), how is the time complexity still O(N)?
Yes even I had the same doubt?..did u got this cleared?...
For each reverse, it only reverse the number of items in that level. If you look at how many total items are being reversed, it’s roughly half of them, so O(n/2) which can simplify to O(n). So really, we’re just doing O(n) extra work so O(n)+O(n)=O(2n) = O(n).
Think about it more in terms of filling the array, which is O(n), and then performing a reversal on the entire array on after filling it. This is still O(n).
@@chirpy7961look at my solution
For that len(q) thing, U could have made this solution recursive to make in language independent innit?
Shouldn't the time complexity be O(n^2) since half of the height of the tree your are reversing the level. It the tree is a perfect binary tree the last level is size n/2 which effectively is n. If we are reversing the nodes of each level that is odd, then at worst we get closer to O(n^2). This is my conclusion, not sure why we shouldn't take into consideration the reversal part.
A totally useless optimization we can make to not have to reverse odd indexed arrays, is to use the double sided constant time addition/deletion property thing of a deque.
Basically,
if we are going from left -> right i.e. popping from beginning of the deque, we add the children to the end (left child first then right),
else if we are going from right -> left i.e. popping from the end of the deque, we add the children to the start(right child first then left)
This way we do a zig-zag bfs which kinda feels nauseating to imagine while dry running
That way we visit each node only once, so atmost ~n operations, O(n) TC.