Binary Tree Vertical Order Traversal— LC Medium

Companies: Facebook, Bloomberg, Amazon

314. Binary Tree Vertical Order Traversal

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

My first approach: DFS with hashmap, keeping the tree position row and columns

code:

from collections import defaultdict,deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # DFS implementation
        
        # cover the base case
        
        if not root:
            return []
        
        self.tempDict = defaultdict(list)
        
        self.dfsIterator(root, 0, 0)
        
        # then it is going to have a nested list [[],[],...]
        self.tempDict = dict(sorted(self.tempDict.items()))
ans = []
        
        for k, v in self.tempDict.items():
            ans.append([x[1] for x in sorted(v, key = lambda x: x[0])])
            
        return ans
        
        
    def dfsIterator(self, node, col, row):
        # cover the base case
        if not node:
            return None
        
        if node:
            self.tempDict[col].append((row, node.val))
            self.dfsIterator(node.left, col - 1, row + 1)
            self.dfsIterator(node.right, col + 1, row + 1)
            
    # time complexity: O(N) to iterate through all the nodes, O(NlogN) for using built in sorting function
    # space complexity: O(N) for making list and hashmap
    
    # test case 1: root = [3, 9, 20, null, null, 15, 7]
    # self.tempDict = {} # it goes on to root, which is 3
    # self.tempDict = { 0: [(0, 3)] }
    # recurse to the left with column -1, and at its left, there is 9
    # self.tempDict = { -1: [(1, 9)], 0: [(0,3)]}
    # 9's left or right is all null, so it bounces back due to if clause that covers this case
    # recurse to the right of 3, which is 20
    # self.tempDict = { -1: [(1,9)], 0: [(0, 3)], 1: [(1, 20)]}
    # recurse to 20's left, with col = 0
    # self.tempDict = { -1: [(1, 9)], 0: [(0, 3), (2, 15)], 1: [(1, 20)]}
    # 15 is a leaf node with no left nor right, so it bounces back
    # recurse to 20's right, with col = 2
    # self.tempDict = { -1: [(1, 9)], 0: [(0, 3), (2, 15)], 1: [(1, 20)], 2: [(2, 7)]}
    # 7 is a leaf node with no left nor right, so it bounces back
    # bounce back all the way to 3, and the stored result is on the self.tempDict
    # sort the dictionary with its key value
    # sort the value of the key by the first value (which is row info)
    # return the nested list

Time complexity: O(N)

Space complexity: O(N)

Second approach: BFS level order traversals

from collections import defaultdict,deque
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        # BFS implementation
        
        res = defaultdict(list)
        
        que = deque([(0, root)])
            
        while que:
            col, node = que.popleft()
            
            if node:
                res[col].append(node.val)
                que.append([col - 1, node.left])
                que.append([col + 1, node.right])
                
        res = dict(sorted(res.items()))
return [val for key, val in res.items()]
    
    # Time complexity: O(N)
    # Space complexity: O(N)
    
    # test case 1: root = [3, 9, 20, null, null, 15, 7]
    # res = {}
    # que = deque([0, 3])
    # if node is not None, then it is going to append to the res dictionary with its value
    # que = deque()
    # res = {0: [3]}
    # que = deque([(-1, 9), (1, 20)])
    
    # que = deque([(1,20)])
    # res = {-1: [9], 0: [3]}
    # que = deque([(1, 20), (-2, None), (0, None)])
    
    # que = deque([(-2, None), (0, None)])
    # res = {-1: [9], 0: [3], 1: [20]}
    # que = deque([(-2, None), (0, None), (0, 15), (2, 7)])
    
    # que = deque([(0, None), (0, 15), (2, 7)])
    # res = {-1: [9], 0: [3], 1: [20]}
    # que = deque([(0, None), (0, 15), (2, 7)])
    
    # que = deque([(0, 15), (2, 7)])
    # res = {-1: [9], 0: [3], 1: [20]}
    # que = deque([(0, 15), (2, 7)])
    
    # que = deque([(2, 7)])
    # res = {-1: [9], 0: [3, 15], 1: [20]}
    # que = deque([(2, 7), (-1, None), (1, None)])
    
    # que = deque([(-1, None), (1, None)])
    # res = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}
    # que = deque([(-1, None), (1, None), (1, None), (3, None)])
    
    # que = deque([(1, None), (1, None), (3, None)])
    # res = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}
    # que = deque([(1, None), (1, None), (3, None)])
    
    # que = deque([(1, None), (3, None)])
    # res = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}
    # que = deque([(1, None), (3, None)])
    
    # que = deque([(3, None)])
    # res = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}
    # que = deque([(3, None)])
    
    # que = deque([])
    # res = {-1: [9], 0: [3, 15], 1: [20], 2: [7]}
    # que = deque([])
    
    # while loop breaks, and returns the sorted res.

Time complexity: O(N)

Space complexity: O(N)