[Top Interview 150] 102. Binary Tree Level Order Traversal

Solution)

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # res will be returned at the end
        # queue will save nodes level by level
        res, queue = [], deque()

        if root: queue.append(root)

        # Iterate tree while queue is not empty
        while queue:
            # This temporary list will save values of nodes in each level
            lv = []

            # This for-loop will append the current level nodes' values to lv
            # and save their children nodes in queue
            for i in range(len(queue)):
                cur = queue.popleft()
                lv.append(cur.val)

                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            
            # Append the list of current level nodes' values to res
            res.append(lv)
        
        return res

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)
*n = number of nodes in a tree
 

Explanation)

We'll use BFS approach to solve this problem.
 
We'll use deque from collections to save nodes in each level.
 

Using deque to save nodes in each level

 

1. Base Case & Initialization)

Variable res is a list of level order traversal of all the nodes' values in the tree.
Variable queue is a deque that will save nodes in each level.
 
If the tree is not empty, we'll save root in queue.
We know there is only one node in the first level, meaning our queue has done its job in the current level.
 

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1. Base Case & Initialization
        res, queue = [], deque()
        if root: queue.append(root)

 

2. Save current level nodes' values)

We'll iterate the tree until our queue becomes empty. This allows us to iterate the entire tree.
 
Variable lv will save the values of nodes in the current level.
 
Using a ranged for-loop, we can popleft nodes from queue and append their values to lv.
We popleft so that we can save values of nodes from left to right.
 

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1. Base Case & Initialization
        res, queue = [], deque()
        if root: queue.append(root)

        # 2. Save current level nodes' values
        while queue:
            lv = []

            for i in range(len(queue)):
                cur = queue.popleft()
                lv.append(cur.val)

 

3. Save nodes in the next level)

Now that we saved the values of nodes in the current level, we need to update the nodes.
 
If cur's children exist, append them to queue so that we can use them in next iterations.
 
 
Once the for loop is done, lv has the values in the current level. Append lv to res.
 
Repeat this process until the entire tree is iterated.
 

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1. Base Case & Initialization

        # 2. Save current level nodes' values
        while queue:
            lv = []

            for i in range(len(queue)):
                cur = queue.popleft()
                lv.append(cur.val)
                
                # 3. Save nodes in the next level
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            
            res.append(lv)
        
        return res

---

 
 
 
Practice really does make perfect. I used to hate solving binary trees because I was so bad at it, but now I know what and how to do those problems. Who would've thought. Not me at least :)