102. Binary Tree Level Order Traversal

Problem

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]

Example 2: Input: root = [1] Output: [[1]]

Example 3: Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Solution

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/

Recursion - O(n) time - O(n) space

1. First ensure that the tree is not empty, then call recursively the function helper(node, level), which takes the current node and its level as the arguments.
2. Compare the number of a current level len(levels) with a node level level.
3. If you’re still on the previous level - add the new one by adding a new list into levels.
4. Append the node value to the last list in levels.
5. Process recursively child nodes if they are not None: helper(node.left / node.right, level + 1).

class Solution {
public:
    vector<vector<int>> levels;
    void helper(TreeNode* node, int level) {
        if (levels.size() == level) levels.push_back(vector<int>());
        levels[level].push_back(node->val);
        if (node->left != nullptr) helper(node->left, level + 1);
        if (node->right != nullptr) helper(node->right, level + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return levels;
        helper(root, 0);
        return levels;
    }
};

Queue - O(n) time - O(n) space

Keep nodes of each tree level in the queue structure, which typically orders elements in a FIFO (first-in-first-out) manner.

The zero level contains only one node root. The algorithm is:

• Initiate queue with a root and start from the level number 0: level = 0.
• While the queue is not empty
  • Start the current level by adding an empty list into the output structure levels.
  • Compute how many elements should be on the current level: it’s a queue length.
  • Pop out all these elements from the queue and add them to the current level.
  • Push their child nodes into the queue for the next level.
  • Go to the next level level++.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;
        if (root == NULL) return levels;
        
        deque<TreeNode*> queue;
        queue.push_back(root);
        
        int level = 0;
        
        while (!queue.empty()) {
            // start the current level
            levels.push_back({});
            // number of elements in the current level
            int level_length = queue.size();
            for (int i = 0; i < level_length; ++i) {
                TreeNode* node = queue.front();
                queue.pop_front();
                // fulfill the current level
                levels[level].push_back(node->val);
                // add child nodes of the current level
                // in the queue for the next level
                if (node->left != NULL) queue.push_back(node->left);
                if (node->right != NULL) queue.push_back(node->right);
            }
            // go to next level
            level++;
        }
        return levels;
    }
};