314. Binary Tree Vertical Order Traversal - Explanation

Description

You are given the root node of a binary tree, return the vertical order traversal of its nodes' values.

For the vertical order traversal, list the nodes column by column starting from the leftmost column and moving to the right.

Within each column, the nodes should be listed in the order they appear from the top of the tree to the bottom.

If two nodes are located at the same row and column, the node that appears to the left should come before the other.

Example 1:

Input: root = [1,2,3,4,5,6,7]

Output: [[4],[2],[1,5,6],[3],[7]]

Example 2:

Input: root = [1,2,3,null,4,5,null]

Output: [[2],[1,4,5],[3]]

Constraints:

0 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Breadth First Search + Sorting

# 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]]:
        cols = defaultdict(list)
        que = deque([(root, 0)])

        while que:
            node, pos = que.popleft()
            if node:
                cols[pos].append(node.val)
                que.append((node.left, pos - 1))
                que.append((node.right, pos + 1))

        return [cols[x] for x in sorted(cols)]

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Depth First Search + Sorting

# 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]]:
        cols = defaultdict(list)

        def dfs(node, row, col):
            if not node:
                return
            cols[col].append((row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        res = []
        for col in sorted(cols):
            col_vals = sorted(cols[col], key=lambda x: x[0])
            res.append([val for _, val in col_vals])
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n \log n)$

3. Breadth First Search (Optimal)

# 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 []

        cols = defaultdict(list)
        queue = deque([(root, 0)])
        minCol = maxCol = 0

        while queue:
            node, col = queue.popleft()
            cols[col].append(node.val)
            minCol = min(minCol, col)
            maxCol = max(maxCol, col)

            if node.left:
                queue.append((node.left, col - 1))
            if node.right:
                queue.append((node.right, col + 1))

        return [cols[c] for c in range(minCol, maxCol + 1)]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Depth First Search (Optimal)

# 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 []

        cols = defaultdict(list)
        minCol = maxCol = 0

        def dfs(node, row, col):
            nonlocal minCol, maxCol
            if not node:
                return
            cols[col].append((row, node.val))
            minCol = min(minCol, col)
            maxCol = max(maxCol, col)
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        res = []
        for c in range(minCol, maxCol + 1):
            # sort by row only
            col_vals = sorted(cols[c], key=lambda x: x[0])
            res.append([val for _, val in col_vals])
        return res

Time & Space Complexity

Time complexity: $O(w * h \log h)$
Space complexity: $O(n)$

Where $n$ is the number of nodes, $h$ is the height of the tree (i.e. maximum number of nodes in any vertical line of the tree), and $w$ is the width of the tree (i.e. maximum number of nodes in any of the levels of the tree).