C++ Solution - Using Queues and Separator - Explained
Intuition\nLevel Order Traversal is a BFS Algorithm - BFS algorithms use Queue Data Structure \nIn BFS - we traverse/explore all nodes of a given level and then
# Intuition\n**Level Order Traversal is a BFS Algorithm** - BFS algorithms use *Queue Data Structure* \nIn BFS - *we traverse/explore all nodes of a given level and then move onto the next level*\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. *Level 0* of the tree contains the `root` node only. Insert that into the queue then also insert a separator. \n> Separator - anything that could be used to indicate that a level of tree has been explored. We have used NULL as a separator here\n\n2. Then, iterate through the queue till it gets empty \nStore the front element into a `temp` node.\n\n- `If temp is NULL` -> means the last level has been traversed completely \nPush the vector of stored nodes into the 2-D vector that we have to return \nAlso check if there are still child nodes in the queue i.e., if the queue isn\'t empty then push another separator into the queue \n\n- `If temp is not NULL` - it is a node -> then push the value into a 1-D vector. Also push the left and right child nodes of the node into the queue. \n<!-- Describe your approach to solving the problem. -->\n\n\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    vector<vector<int>> levelOrder(TreeNode* root) {\n        \n        vector<vector<int>> ans ; \n        vector<int> output ;  \n\n        // edge case \n        if (root == NULL)\n        {\n            return ans ; \n        }\n\n        // insert the first element and separator in the vector \n        queue<TreeNode*> q; \n        q.push(root) ;  //insert the first node the root node \n        q.push(NULL) ;  // the first separator comes after root node \n\n        while (!q.empty())\n        {\n            TreeNode *temp = q.front() ; \n            q.pop() ; \n            // if element at the front is a separator means one level has been traversed so we push the 1-D vector storing elements of that level into the 2-D vector that we have to return \n            if (temp == NULL)\n            {\n                ans.push_back(output) ; \n                output.clear() ; \n\n                // also if the queue is not empty meaning there are still child nodes present in it we would enter another separator in the queue \n                if (!q.empty())\n                {\n                    q.push(NULL) ; \n                }\n            }\n            // else if temp is not NULL\n            else\n            {\n                // insert elements into the 1-D vector \n                output.push_back(temp -> val) ;\n                // also check if the left and right nodes of temp are not NULL then insert them into queue as well\n                if (temp -> left != NULL)\n                {\n                    q.push(temp -> left) ;\n                }\n\n                if (temp -> right != NULL)\n                {\n                    q.push(temp -> right) ; \n                }\n            }\n        }\n        return ans ; \n    }\n};\n```\n![815a317f-9cdf-46e2-a397-af8869dafa2e_1673498197.3721023.png](https://assets.leetcode.com/users/images/0055bde1-7a16-43e2-bc0a-7f392aa66365_1676306691.1136808.png)\n
['Tree', 'Breadth-First Search', 'Binary Tree', 'C++']