✅ Binary Tree Level Order Traversal | Easy Solutions using BFS and DFS Traversals
\u2714\uFE0F Solution - I (BFS Traversal Using Queue)\n\nThe most obvious solution that comes to mind is to use BFS traversal using queue to perform a level ord
\u2714\uFE0F ***Solution - I (BFS Traversal Using Queue)***\n\nThe most obvious solution that comes to mind is to use **BFS traversal** using queue to perform a level order traversal. \n\nWe will start by pushing the root node into the queue and start a loop till the queue becomes empty. \n\nNow, for each node of the tree at any arbitrary level, we will first visit that node from the queue and pop it off. Then we push its left and then right children (since we are required to traverse from left to right) into the queue. This process will repeat for each level of binary tree.\n\nIn a normal binary tree BFS traversal, the above simple process would suffice but here, we are required to distinguish between each level and group all nodes of a level into different vectors. For this, we will use another inner loop. We will take the size of queue **`n`** and iterate the above process `n` times. The only addition here would be - with each **pop** from the queue, we will also **push that node into curLevel** array denoting all nodes on current level. \n\nIn the above process, after `n` iterations, **we have basically visited all the nodes on the current level and pushed all the nodes (from left-to-right) of the next level into the queue**, thus preparing us to traverse the next row as well. This above process will repeat till the queue becomes empty\n\n**C++**\n```\nvector<vector<int>> levelOrder(TreeNode* root) {\n\tif(!root) return {};\n\tqueue<TreeNode*> q;\n\tvector<vector<int> > ans;\n\tq.push(root);\n\twhile(!q.empty()) {\n\t\tint levelSize = size(q);\n\t\tvector<int> curLevel;\n\t\tfor(int i = 0; i < levelSize; i++) {\n\t\t\tauto top = q.front(); q.pop();\n\t\t\tif(top -> left) q.push(top -> left);\n\t\t\tif(top -> right) q.push(top -> right);\n\t\t\tcurLevel.push_back(top -> val);\n\t\t}\n\t\tans.push_back(move(curLevel));\n\t}\n\treturn ans;\n}\n```\n\n---\n\n**Python**\n```\ndef levelOrder(self, root: TreeNode) -> List[List[int]]:\n\tif not root: return []\n\tq, ans = deque([root]), []\n\twhile len(q):\n\t\tn, curLevel = len(q), []\n\t\tfor i in range(n):\n\t\t\tcur = q.popleft()\n\t\t\tif cur.left: q.append(cur.left)\n\t\t\tif cur.right: q.append(cur.right)\n\t\t\tcurLevel.append(cur.val)\n\t\tans.append(curLevel)\n\treturn ans\n```\n\n***Time Complexity :*** **`O(N)`**, where *`N`* is the number of nodes in the binary tree.\n***Space Complexity :*** **`O(N)`**\n\n---\n\n\u2714\uFE0F ***Solution - II (DFS Traversal)***\n\nWe can also use a DFS traversal to solve this problem. Here, we would need to maintain a `depth` variable that tells us the current depth we are at. This allows us to push the current node into the *`ans`* vector at its correct depth (*`ans[depth]`*).\n\nAt each depth, **if this is the first time we are visting this deep, then push an empty vector into *`ans`***. This would allow us to index the current depth and push the node into `ans` at its correct depth. Then continue with the DFS traversal as usual.\n\n**C++**\n```\nvector<vector<int> > ans;\nvector<vector<int>>& levelOrder(TreeNode* root, int depth = 0) {\n\tif(!root) return ans;\n\tif(depth == size(ans)) ans.push_back({});\n\tans[depth].push_back(root -> val);\n\tlevelOrder(root -> left, depth + 1);\n\tlevelOrder(root -> right, depth + 1);\n\treturn ans;\n}\n```\n\n---\n\n**Python**\n```\ndef levelOrder(self, root: TreeNode) -> List[List[int]]:  \n\tans = []\n\tdef dfs(root, depth):\n\t\tif not root: return\n\t\tif len(ans) == depth: ans.append([])\n\t\tans[depth].append(root.val)\n\t\tdfs(root.left, depth + 1)\n\t\tdfs(root.right, depth + 1)\n\tdfs(root, 0)\n\treturn ans\n```\n\n\n***Time Complexity :*** **`O(N)`**, where *`N`* is the number of nodes in the binary tree.\n***Space Complexity :*** **`O(N)`**\n\n---\n\n*Better Solution - BFS vs DFS?*\n\uD83D\uDC49 Choose **DFS** if you know that the trees would generally be more balanced (full tree or complete tree or close). This would give worst case space complexity of `O(h)` in case of DFS instead of `O(2^h)` in case of BFS, where *`h (=O(logn))`* is the height of tree. \n\n\uD83D\uDC49 Choose **BFS** if you know that tree are skewed and there might be some branches that go deep. This would give space complexity of `W` (`W` = max width / nodes on a level ) in case of BFS instead of `O(n)` in case of DFS.\n\nNeither will be always better over the other. Here, since the question specifically asks for level order traversal, I think the first solution is more intuitive and applicable in this case.\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C', 'Python']