Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Key Takeaways
The video demonstrates a solution to the Leetcode 103 problem, Binary Tree Zigzag Level Order Traversal, using a breadth-first search algorithm in Python. The solution iterates through the binary tree level by level, adding each level to the result array and reversing every odd level.
Full Transcript
hey everyone welcome back and let's write some more neat code today so today let's solve the problem binary tree zigzag level order traversal we're given the root of a binary tree and we just want to do something pretty simple we want to take every single level put it into an array when we say put it into we mean the value so the first level is three the second level is 9 and 20 and the third level is 15 and 7. we just want to take every level put it into an array like this one and this one and this one and then add all of these arrays into like a final array and then return them the only catch is that each one at an odd index is going to be reversed so this one is going to be reversed meaning it's actually going to be 29. the levels at an even index will will stay the same so that's pretty much it that's the problem so first of all how can we iterate through a binary tree level by level we're used to doing DFS which uses recursion but now to do it this way the better algorithm to use is breadth first search which is usually not recursive usually breadth first search just goes through every single level left to right so how do we do this zigzag where sometimes we're going to go in reverse direction should we just keep track of what level we're at and then Traverse through that level in Reverse well that's definitely possible but that turns out to be a bit more complicated than we need because why not just go through each level from left to right but when it comes time to take this array which is 9 20 and then add it to our overall result when this time comes why not just take every odd level and then reverse this change it to 29 and then add it to the result yes we sort of have to go through each level twice one to actually build the level and then one to reverse it but that doesn't change the overall time complexity which is usually what we try to optimize for so the overall time complexity Still Remains Big O of N I guess we're visiting every node twice but that doesn't change the overall time complexity magnitude the space complexity is going to also be Big O of n breath for a search usually is an algorithm that takes a q data structure the max size of the queue is going to be at most the max level in our binary tree and when we have a binary tree maybe the first level has one node the second level has two nodes the third level has four nodes each level in the worst case could double in length and if the bottom level is full like this one hey it's gonna be roughly half the size of the tree as you can see this is basically where the space complexity comes from so if the worst case space complexities n divided by 2 which is what this Q might be maybe we have this entire Q in memory well n divided by 2 is just going to be Big O of n we don't care about constants so this is the space complexity of breadth first search on a binary tree now let's code it up so I've written breadth first search so many times that my brain is kind of on autopilot but I'll try to explain this we're going to initialize our result to be an empty array we want to add every level to this result we also are going to do breadth for search and to do that we need a q in Python you can use a deck and we want to initialize it with the root but we probably don't want to add the root if it's null so what we can do is something like this where we'll initialize it with just the root if root is non null else we will just add an empty array to it which is basically to say that the deck will be empty the queue will be empty or it will just have the root on it this is the ternary operator in Python if you're not familiar but now let's actually do the breadth first search so while the Q is non-empty then we're gonna build the current level we're gonna go level by level because we actually have to keep track of what level that we are on and then I'm gonna go through every node in this current level so for I in range the length of the Queue at this point in time now if you usually write this in other languages pay attention to this because this is a bit different this will only be called once and it'll snapshot the queue so maybe the queue initially has two items in it maybe the length just has two values in it so the length of the queue is equal to two then inside this Loop if we add to the Q that's not going to change this because range is a function if we pass in 2 to it once it's not going to update as we run it this is equivalent to if I had a variable like length and just initialized it once I just took a snapshot of the queue and then I passed length in here that's how it is in Python but I know in most languages it's different so I just wanted to explain that but now for the interesting part we're going to pop every node from the queue and we're going to do so from the left because we're going to be pushing to the right so we pop from the left of the queue we get a node we know this node is going to be non-null because well we checked that when we added the root and I'm going to have some checks here when we add its children but let's assume we know we're never going to push null onto the queue so assuming this node is non-null we're going to take its value and append that to the current level and then we're going to take the children of the node only if they're non-null so if left is non-null we take the Q 2 and a pen to it the node dot left the left note if node dot right is non-null then we're gonna append to the Q node dot right so this will go through the entire level and put all the values in the array and at that point all we want to do is take the level and append it to the array but there's a catch every odd level we want to reverse the level how do we do that well you could have a separate variable to keep track of the current level but it's actually even easier because we have our result the result will tell us how many levels we have seen so far so we know we are going to reverse the level if the length of the result modded by 2 is equal to one because that tells us that for example if the length is equal to one that means we are at index 1 so that means this would be odd and that is the case that we would want to reverse this if the length is equal to 2 then modding that is going to be equal to zero and that works because if the length is 2 that means we're at index two and it for even indexes we don't want to reverse this so in the else case with this ternary operator we are going to set it just equal to the level so either we reverse it on odd levels or we leave the level the same and then we append it to the result after all of this will have gone through every single level and the queue will be empty so then we can go ahead and return the result so now let's run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon
Original Description
🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews
Solving Leetcode 103 - Binary Tree Zigzag Level Order Traversal, today's daily leetcode problem.
🥷 Discord: https://discord.gg/ddjKRXPqtk
🐦 Twitter: https://twitter.com/neetcode1
🐮 Support the channel: https://www.patreon.com/NEETcode
⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf
💡 DYNAMIC PROGRAMMING PLAYLIST: https://www.youtube.com/watch?v=73r3KWiEvyk&list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO&index=1
Problem Link: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
0:00 - Read the problem
0:50 - Drawing Explanation
3:23 - Coding Explanation
leetcode 103
#neetcode #leetcode #python
Watch on YouTube ↗
(saves to browser)
Sign in to unlock AI tutor explanation · ⚡30
Playlist
Uploads from NeetCodeIO · NeetCodeIO · 33 of 60
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
▶
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
Design Linked List - Leetcode 707 - Python
NeetCodeIO
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
LFU Cache - Leetcode 460 - Python
NeetCodeIO
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
IPO - Leetcode 502 - Python
NeetCodeIO
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
Sort an Array - Leetcode 912 - Python
NeetCodeIO
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO
More on: Algorithm Basics
View skill →
Related AI Lessons
⚡
⚡
⚡
⚡
Bloom Filters, Explained Properly
Dev.to · Daksh Gargas
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Medium · Programming
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
Medium · Programming
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Medium · Python
Chapters (3)
Read the problem
0:50
Drawing Explanation
3:23
Coding Explanation
🎓
Tutor Explanation
DeepCamp AI