O(n) Time O(n) Space
Intuition\nThis is a standard Tree traversal. There are two types of tree traversals, BFS and DFS. DFS can be broken out into 3 other traversals, InOrder, PreOr
# Intuition\nThis is a standard Tree traversal. There are two types of tree traversals, BFS and DFS. DFS can be broken out into 3 other traversals, InOrder, PreOrder, and PostOrder. This is a BFS, level order traversal.\n\nTwo simple ways would be recursively and iteratively. I find recursive to be awkward for BFS so I prefer iterative. At each level, the queue count dictates the number of nodes on that level.\n\n# Approach\n1. Use a Queue\n2. At each level, track the queue count and then iterate through that many nodes for just that level\n3. Add nodes to the current level of the result and Enqueue the left/right nodes for the upcoming level\n4. Advance the level\n\n# Complexity\n- Time complexity:\n$$O(n)$$\n\n- Space complexity:\nBest case: Skewed Binary Tree: $$O(1)$$. At each level, you would enqueue only 1 node.\nWorse case: Perfect Binary Tree: $$O((n-1)/2 + 1)$$ ~ $$O(n)$$. Imagine there are 7 nodes in the tree. In a perfect binary tree, that would mean 4 nodes on the 3rd level which means the queue will have at most 6/2 + 1 nodes. For 15 nodes, that\'s 8 nodes on the 4th level, which means the queue will have at most 14/2 + 1 nodes. Regardless, it\'s still $$O(n)$$, but could be worth mentioning that you understand the queue never contains more nodes than the max level in a perfect binary tree.\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\npublic class Solution {\n    public IList<IList<int>> LevelOrder(TreeNode root) {\n        IList<IList<int>> result = new List<IList<int>>();\n        if (root == null) {\n            return result;\n        }\n\n        Queue<TreeNode> queue = new Queue<TreeNode>();\n        queue.Enqueue(root);\n\n        while (queue.Count > 0) {\n            int count = queue.Count;\n            List<int> level = new List<int>();\n\n            for (int i = 0; i < count; i++) {\n                TreeNode cur = queue.Dequeue();\n                level.Add(cur.val);\n\n                if (cur.left != null) {\n                    queue.Enqueue(cur.left);\n                }\n                if (cur.right != null) {\n                    queue.Enqueue(cur.right);\n                }\n            }\n\n            result.Add(level);\n        }\n\n        return result;\n    }\n}\n```
['Breadth-First Search', 'Binary Tree', 'C#']