Leetcode: Level Order

Binary Tree Level Order Traversal | LeetCode OJ

This is one of the main traversals of trees that you would come across in many other places. For example, Pascal’s triangle can be fit into the same question. Please visit the blog on Pascal’s triangle to know more about the question.

Algorithm is pretty straight forward, use the nodes in the current level to get the nodes in the next level

1. Use a queue to store all nodes at a level and initialize it with root
2. As long as there is a level in the queue perform the below steps
3. Add values of all nodes in the current level to result
4. Repopulate the queue with children of nodes in the current level

Remarks:

1. Like all tree algorithms, we are going over all the nodes hence the time complexity is O(n)
2. In the result we store values of all the nodes hence the space complexity is O(n)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: return []
        res, st = [], [root]
        while st:
            res.append([node.val for node in st])
            st = [child for node in st for child in (node.left, node.right) if child]
        return res