[LeetCode] Binary Tree Level Order Traversal

 

 

Problem

 

---

 

Recursive Solution

 

This problem is somewhat like BFS, except that we need to examine every node on the same level before expanding.

Since the first element of a level is a left child of some node, first traverse down the left subtrees and store the values. Then examine the right nodes while coming back up.

After coming back to the root, go to the right subtree and examine the left nodes in the same manner while going down.

 

 

Time Complexity

O(N) (every node is processed once)

 

 

Space Complexity

O(N) (result array)

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if not root:
            return result
        
        self.traverse(root, 0, result)
        return result
        
    
    def traverse(self, node, level, result):
        if len(result) == level:
            result.append([])
        
        result[level].append(node.val)
        
        if node.left:
            self.traverse(node.left, level + 1, result)
        if node.right:
            self.traverse(node.right, level + 1, result)

 

 

 

Iterative Solution

 

Need a FIFO queue so that the nodes on the next level are stored from left to right, and then examined in order from left to right.

 

Time Complexity

O(N)

 

 

Space Complexity

O(N)

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # BFS
        # look at current node, put all connected nodes into stack, pop the stack and assign the value to current node, and repeat
        if not root:
            return []
        
        levels = []
        thisLevel = deque()
        
        thisLevel.append(root)
        while thisLevel:
            currentNodes = []
            nextNodes = deque()
            while thisLevel:
                curr = thisLevel.popleft()
                if curr is not None:
                    currentNodes.append(curr.val)
                    nextNodes.append(curr.left)
                    nextNodes.append(curr.right)
            if currentNodes:
                levels.append(currentNodes)
            thisLevel = nextNodes
                
        return levels