Level Order Traversal - Binary Tree
We can do a level order traversal of a binary tree (i.e. visit first level left-to-right, then second level left-to-right, and so on all the way down to the last level) using a queue. Here's a possible implementation:
void levelOrder(Node *root) {
if (root == nullptr) return;
queue<Node *> qu;
qu.push(root);
while (!qu.empty()) {
Node *curr = qu.front();
qu.pop();
cout << curr->value << '\n';
if (curr->left != nullptr) {
qu.push(curr->left);
}
if (curr->right != nullptr) {
qu.push(curr->right);
}
}
}
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.