Today’s Leetcode July Challenge puts a minor twist on a classic traversal algorithm. The problem gives us a binary tree and asks us to return a zigzag level order traversal of the tree. A zigzag traversal is defined by alternating the traversal from left to right and right to left from one level to the next, where the root node is considered left to right. Here’s an example of what that looks like:

Input:

graph TD; 1((1))---2((2)) 1((1))---3((3)) 2((2))---4((4)) 2((2))---5((5)) 3((3))---6((6)) 3((3))---7((7))
Output: [[1],[3,2],[4,5,6,7]]

This only requires a slight modification to my typical level-order traversal algorithm. The typical algorithm uses a queue to store the nodes of a given level and a counter to pop off only the elements belonging to the current level on each iteration. There are a couple of ways to achieve the zigzag pattern. The easiest method is just to reverse any right to left levels after building them in the typical left to right fashion. We can make a slight improvement by building each level in place, in its final order. There aren’t any particular edge cases worth mentioning apart from an empty tree. The two general cases are a full tree and a sparse tree.

Here’s the first approach where we just reverse the level after building it left to right:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
   if(!root) return {};
   vector<vector<int>> zigzag;
   queue<TreeNode*> q;
   q.push(root);
   bool zig = true;
   
   while(!q.empty()) {
	  int length = q.size();
	  vector<int> level;
	  for(int i=0;i<length;i++) {
		 TreeNode* tmp = q.front();
		 q.pop();
		 level.push_back(tmp->val);
		 if(tmp->left) q.push(tmp->left);
		 if(tmp->right) q.push(tmp->right);
	  }
	  if(!zig) reverse(level.begin(), level.end());
	  zigzag.push_back(level);
	  zig = !zig;
   }
   return zigzag;
}

and a slight variation where we build the level in place:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
   if(!root) return {};
   vector<vector<int>> zigzag;
   queue<TreeNode*> q;
   q.push(root);
   bool zig = true;
   
   while(!q.empty()) {
	  int length = q.size();
	  vector<int> level(length,0);
	  for(int i=0;i<length;i++) {
		 TreeNode* tmp = q.front();
		 q.pop();
		 
		 level[zig?i:length-i-1] = tmp->val;
		 if(tmp->left) q.push(tmp->left);
		 if(tmp->right) q.push(tmp->right);
	  }
	  zigzag.push_back(level);
	  zig = !zig;
   }
   return zigzag;
}

So, that’s a little twist on a basic problem. Both algorithms have an asymptotic runtime complexity of O(n) and use O(n) memory, as a full binary tree will have N/2 nodes at the bottom/leaf level. For a challenge, you can try implementing the algorithm as a depth-first search in order to reduce the space complexity O(log n).