Leetcode 102 - Binary Tree Level Order Traversal

BFS

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        
        if root is None:
            return res
        
        q = collections.deque()
        q.append(root)                    # use queue data structure since this is a BFS - it goes from left to right. 
        
        while q:
            qLen = len(q)                  # to ensure we're looping through one level at a time.
                                           # qLen represents the length of the nodes in each level. 
            
            level = []                     # current level 
            for i in range(qLen):
                node = q.popleft()
                if node:
                    level.append(node.val) # appending the node value to the current level. 
                    q.append(node.left)    # inserting left child.
                    q.append(node.right)   # inserting right child. 
            if level:                      # checking whether the level is null. 
                res.append(level)
        return res

 

DFS

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels = []
        
        if root is None:
            return res
        
        def dfs(node, level):
            if len(levels) == level:
                levels.append([])
            
            # append the current node value

            levels[level].append(node.val)
            
            # process child nodes for the next level
            # 'level + 1' is for moving to the level
            if node.left:
                dfs(node.left, level + 1)
            if node.right:
                dfs(node.right, level + 1)
                
        dfs(root, 0)
        return levels