Spiral Level Order Traversal - Binary Tree

We can do a spiral level order traversal of a binary tree (i.e. visit first level left-to-right, then visit second level right-to-left, then visit third level left-to-right, and so on, alternating each level) using two stacks. Here's a possible implementation:

void spiralLevelOrder(Node *root) {
  if (root == nullptr) return;

  stack<Node *> st1, st2;
  st1.push(root);
  while (true) {
    while (!st1.empty()) {
      Node *curr = st1.top();
      st1.pop();
      cout << curr->value << '\n';
      if (curr->left != nullptr) {
        st2.push(curr->left);
      }
      if (curr->right != nullptr) {
        st2.push(curr->right);
      }
    }
    if (st2.empty()) break;

    while (!st2.empty()) {
      Node *curr = st2.top();
      st2.pop();
      cout << curr->value << '\n';
      if (curr->right != nullptr) {
        st1.push(curr->right);
      }
      if (curr->left != nullptr) {
        st1.push(curr->left);
      }
    }
    if (st1.empty()) break;
  }
}

Time complexity

The time complexity is O(n) (where n is the number of nodes in the tree) because of the work we do in the two while loops. See the video for more detail.

Space complexity

The space complexity is O(n) (where n is the number of nodes in the tree) because of the space taken by the two stacks. See the video for more detail.

Video with explanation