Binary Tree Zigzag Level Order Traversal | Leet code 103 | Theory explained + Python code

This video is a solution to Leet code 103, Binary Tree Zigzag Level Order Traversal. I first give a theoretical explanation and then I go over its Python implementation.

Comment below if you have a better solution to this problem!

Let me know if you have any feedback and don't forget to subscribe for more videos!

Gear used:

[jimwoodward]

Nice explanation and clear code walk through -- thanks!

[aravindkumar]

instead of two if loops to append both node.left and node.right to stack everytime, you can try this optimized code of stack+= filter(None, (node.left, node.right))

[tariqelamin]

Great explanation, but this is a Queue, not a stack because you're actually taking out the last element you inserted even tho you are using .pop() you still removing the last element you have inserted so it acts as a queue.

[kinenehenry]

Used a different approach, did the normal bfs then flipped the odd indexed elements


def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:


levels=[]
if not root:
return levels
def helper(node, level):
if len(levels)==level:
levels.append([])

if node.left:
helper(node.left, level+1)
if node.right:
helper(node.right, level+1)
helper(root, 0)
for i in range(len(levels)):
if i%2==0:
levels[i]=levels[i]
else:
levels[i]=levels[i][::-1]
return levels

[jyotijangid]

Very precise, clear, and easy explanation. Just one thing when I did the same thing but by creating a queue using collections.deque and then pop left, the runtime increased drastically while in-build ds generally decreases the runtime? why