Binary tree level order traversal - Python3 Solution with a Detailed Explanation
Here, since we\'re doing a level order traversal (read this if you don\'t know what it means), we\'d be better of using breadth first search algorithm. Think ab
Here, since we\'re doing a level order traversal (read [this](https://towardsdatascience.com/4-types-of-tree-traversal-algorithms-d56328450846) if you don\'t know what it means), we\'d be better of using breadth first search algorithm. Think about it? What you want to do for level order traversal? At each level, you go from left to right, and add nodes to the output list `res`, right? We start from `root`, add it to `res`, go to a deeper level, add the left node, add the right node! go to a deeper level, do the same until there is no other node. Now, thinkg about using what data structure we could do this? We need a data structure that could be used to add nodes to them in a first come first serve way! Meaning, if you visit the left node first, you\'ll see this in `res` first, regardless of what you\'ve seen after that. This is First In First out appraoch, and `queue` data structure could easily do this. That\'s what we\'re using here. \n\n\nWhat we do is to make a `queue`. The `queue` keeps every node is the current level. For example, initially the `root` node gets added to the `queue`. Then within a `while` loop, we `pop(0)` is the first element of `queue` (the element that was added the first). Then, we go over all element of `queue` and pop them one by one. Each popped element will be added to `level` which keeps track of nodes in the current level. For example, when we `pop(0)` the `root` node, we want to add the children of `root`, right? That\'s why we check whether `left` and `right`  nodes exist. If they do exist, we add them to the `queue`. Note that although `queue` size changes, it doesn\'t affect the current `for` loop. But, once the current `for` loop ends, the new size of `queue` will be used next time the `for` loop starts to go over `queue` from start. Finally, at the end of each `for` loop (meaning that the current level is taken care of and all the nodes of current level are added to `level` variable), we append the `level` variable to `res`. We keep doing this until `queue` is empty, meaning that all nodes have been visited. Now, we go out of `while` loop and return `res` as the final output. \n\n\n\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n        \n        if root is None: # if root is None, there is no deeper level to go to. Then, return [] which is the root. \n            return root\n        \n        res = [] # final output\n        queue = [] # keep track of nodes in each level from left to right\n        queue.append(root) # first node (root) is added to queue which we\'ll be later added to level and then finally res\n        \n        while len(queue) > 0: # we keep going until there is something in queue. Empty queue means we have covered every node\n            level = [] # This collects every node is each level. Note the output format in the problem statement. Nodes of each level are a sublist within the final output list res\n            for i in range(len(queue)): # it goes over length of queue which includes all the elements of current level, and each of them is added to the level variable. \n                node = queue.pop(0) # removes the first element of the list. In contrast to pop() that removes last element and is used for stack data structure. Note that first element is added \n                level.append(node.val) # append the value of current node\n            \n                if node.left != None: # queue gets updated by adding left child. The traversal occurs from left to right\n                    queue.append(node.left)\n                if node.right != None: # queue gets updated by adding right child. \n                    queue.append(node.right)\n            res.append(level) # we\'re done with this level, and we append level to the res variable\n        return res\n```\n\nThere are other ways of approaching problem. [caikehe](https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33731/Python-short-dfs-solution)\'s recursive solution is one of them. He has solved a lot of problems using the same appraoch (not just for graphs/trees). It\'s good to make sure you get the logic. The main function is just a wrapper for `dfs` function. `dfs` accepts three variables as input. If the `root` is `None`, then return. \n\n\n\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution:\n    def levelOrder(self, root):\n        res = []\n        self.dfs(root, 0, res)\n        return res\n    \n    def dfs(self, root, level, res):\n        if not root:\n            return \n        if len(res) < level+1: # For example, if you\'re at root, nothing has added to res and its length is zero. You add the [] to later add the number in in. This is true for other deeper layers. \n            res.append([])\n        res[level].append(root.val)\n        self.dfs(root.left, level+1, res) # the left node\n        self.dfs(root.right, level+1, res) # add the right node\n\t\t\n```\n\n\nThat\'s it!!\n\n===================================================================\nFinal note: Please let me know if you found any error/typo/etc. I\'ll try to fix it. \n\n\n\n\n
['Python', 'Python3']