Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7

return its level order traversal as: [ [3], [9,20], [15,7] ]

Solution: Recursive with depth

In this solution, we traverse the tree in preorder, but we also pass the depth as a parameter. We use depth to find the level vector and push the node to the corresponding vector.

void levelOrderUtil(TreeNode *root, int depth, vector<vector<int>> &ans) {
    if (!root) return;
    if (ans.size() == depth) ans.push_back({});

    ans[depth].push_back(root->val);
    levelOrderUtil(root->left, depth+1, ans);
    levelOrderUtil(root->right, depth+1, ans);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    levelOrderUtil(root, 0, ans);
    return ans;
}

Solution: Count the nodes at current level.

We count the nodes at current level. And for every node, we enqueue its children to queue.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};

    queue<TreeNode *> q;
    vector<vector<int>> ans;
    q.push(root);

    while (true) {
        int nodeCount = q.size();
        if (nodeCount == 0) break;

        ans.push_back({});
        while (nodeCount > 0) {
            TreeNode *node = q.front();
            ans.back().push_back(node->val);
            q.pop();

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
            nodeCount--;
        }
    }

    return ans;
}

Solution: Using two queue

We can insert the first level in first queue and print it and while popping from the first queue insert its left and right nodes into the second queue.

vector<vector<int>> levelOrder(TreeNode* root) {
    if (!root) return {};

    vector<vector<int>> ans;
    queue<TreeNode *> q1, q2;
    q1.push(root);

    while (!q1.empty() || !q2.empty()) {
        if (!q1.empty()) ans.push_back({});            
        while (!q1.empty()) {
            TreeNode *node = q1.front();
            q1.pop();

            if (node->left) q2.push(node->left);
            if (node->right) q2.push(node->right);
            ans.back().push_back(node->val);
        }

        if (!q2.empty()) ans.push_back({});
        while (!q2.empty()) {
            TreeNode *node = q2.front();
            q2.pop();

            if (node->left) q1.push(node->left);
            if (node->right) q1.push(node->right);
            ans.back().push_back(node->val);
        }
    }

    return ans;
}