Binary Tree Zigzag Level Order Traversal

Medium- Hard, https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/solution/

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

During interview:

  1. Its good to point out the differences in the space complexity of the BFS (using a queue) and DFS (recursion ) approaches.
  2. Both solutions are below.