Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values, that is, level by level from left to right, as a list of lists.
Constraints:
- The number of nodes is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Intuition
Every example below uses this tree:
1 12 / \3 2 34 / \ \5 4 5 6The expected output here is [[1], [2, 3], [4, 5, 6]].
Preorder, inorder and postorder go deep first (DFS). Level order goes wide first (BFS): finish everything at depth 0, then depth 1, then depth 2. The tool for that is a queue, because the first node discovered at a level should be the first one processed, and its children line up behind the nodes already waiting.
Approach: BFS with a Queue
- If the tree is empty, return an empty list.
- Put the root in a queue.
- While the queue is not empty:
- Let
sizebe the current queue length. Thosesizenodes are exactly one level. - Pop
sizenodes one by one, adding each value to alevellist, and push each node's left then right child into the queue. - Add
levelto the answer.
- Let
Snapshotting size before the inner loop is the key detail. Children pushed during the loop belong to the next level, so they must not be counted in this round.
Code
class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if (root == nullptr) return ans;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();vector<int> level;for (int i = 0; i < size; i++) {TreeNode* node = q.front();q.pop();level.push_back(node->val);if (node->left != nullptr) q.push(node->left);if (node->right != nullptr) q.push(node->right);}ans.push_back(level);}return ans;}};
Complexity
Each node is pushed into the queue once and popped once.
The queue holds at most one full level, where w is the maximum width of the tree. That is up to about n over 2 nodes for a complete tree, so O(n) in the worst case.