Print Level by Level - Binary Tree

We can print a binary tree level by level (i.e. print the first level left-to-right followed by a new line, then print the second level left-to-right followed by a new line, and so on all the way to the last level) using a queue. The algorithm we use to do this is very similar to the one that we use to do a level order traversal. The main difference is that we use a delimiter that is added to the queue so that we know when to print a new line. Here's a possible implementation:

static Node * const DELIMITER = nullptr;

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

  queue<Node *> qu;
  qu.push(root);
  qu.push(DELIMITER);
  while (true) {
    Node *curr = qu.front();
    qu.pop();
    if (curr != DELIMITER) {
      cout << curr->value << ' ';
      if (curr->left != nullptr) {
        qu.push(curr->left);
      }
      if (curr->right != nullptr) {
        qu.push(curr->right);
      }
    }
    else {
      cout << '\n';
      if (qu.empty()) break;
      qu.push(DELIMITER);
    }
  }
}

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 while loop. 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 queue. See the video for more detail.

Video with explanation