C++: Binary Tree Level Order Traversal

Thought Process

To traverse a binary tree level by level, we can do Breadth-First Search (BFS) traversal of the tree. We start by adding the root node to the queue. At each step, we determine the number of nodes at the current level, which is equal to the queue's size before processing begins. Then, we process each node one by one by removing it from the queue, storing its value in a temporary list, and adding its children (if any) to the queue for the next level. This process repeats until the queue is empty, ensuring that nodes are visited level by level in an efficient manner. 

/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        // root is a pointer to treeNode

        vector<vector<int>> ans;
        queue<TreeNode*> q;

        if(root == NULL)
            return ans;  

        q.push(root);

        while(!q.empty()){

            int noOfNodesatXLevel = q.size();

            vector<int> tmp;
            for(int i=0;i<noOfNodesatXLevel;i++){

                TreeNode* nod = q.front(); q.pop();
                tmp.push_back(nod->val);

                if(nod->left != NULL)
                    q.push(nod->left);

                if(nod->right != NULL)
                    q.push(nod->right);
            }
            ans.push_back(tmp);
        } 
        return ans;    
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(n)

The space used by the queue depends on the maximum number of nodes at any level. In the worst case, the space complexity is O(n).

Code copied!