Leetcode 314: Binary Tree Vertical Order Traversal

Bread-first search (BFS) with queue; Column index tracking with hash table

Problem description

Key tricks

1. BFS to establish column index: The level order traversal of BFS (top to bottom; left to right) gives us two things that we need — First is the mapping between level and column index (increase from left to right at each level) needed to present the vertical ordering results; second is the BFS’s top-to-bottom, left-to-right traversal also naturally allows the following requirement to be met:

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

Figure 1 illustrates the relationship between parent’s and children’s column indexes —

Figure 1: Example of column index (numbers in circles denote column index, not node values, in this example). Left child’s column index = parent’s column index — 1; Right child’s column index = parent’s column index. Each child only needs to know about its parent’s column index. The layout of the binary tree naturally allows us to achieve vertical alignment this way.

2. Hash table (denoted with variable column_table = {<column_index>: <list of ordered node values>}) to keep track of the mapping between nodes and column index as we carry out BFS traversal.

3. Avoid sorting by using minimum and maximum column indices.

BFS refresher: Deque node, Enque children

As previously mentioned in Leetcode 662’s explainer, a FIFO queue is the preferred data structure to facilitate BFS. However, for this problem, we store both the node value and corresponding column index in the queue.

Python solution

Putting these pieces together — BFS with queue; hash table for tracking the mapping between column indexes and nodes, we get the following solutions:

from collections import defaultdict, deque
from typing import List, Optional


class TreeNode:
    """Definition for a binary tree node"""

    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]]:
        # Edge case handling: empty tree
        if not root:
            return []

        # Initiate hash table whose key is the column index and values
        #   are a list of node values in that column
        # Use defaultdict with default type list for conciseness
        column_table = defaultdict(list)

        # Initialize queue
        # Each element is a tuple with (node, column_index)
        queue = deque([(root, 0)])

        min_column = max_column = 0

        # Start BFS traversal
        while queue:
            # Deque parent
            node, column = queue.popleft()
            min_column = min(min_column, column)
            max_column = max(max_column, column)

            column_table[column].append(node.val)

            # Enque children
            if node.left:
                # Left child col = parent col - 1
                queue.append((node.left, column - 1))
            if node.right:
                # Right child col = parent col - 1
                queue.append((node.right, column + 1))

        return [
            column_table[sorted_column]
            for sorted_column in range(min_column, max_column + 1)
        ]

Space and time complexity

With n denoting the total number of nodes in the tree:

• Space complexity:

1. Queue queue takes O(n) space for BFS

At most, we would store all nodes of a particular level in the queue. The maximum space the queue takes is O(w), where w is the maximum width of the tree. In the worst case (i.e., a complete binary tree), w is approximately n/2 where n is the number of nodes. Therefore, the space complexity for the BFS queue is O(n)

2. Hash table column_table takes O(n) space

3. Output array takes O(n) space

Collectively, O(n) + O(n) + O(n) = O(n) space

• Time complexity:

1. BFS traverses through each node takes O(n) time
2. Updating hash table in the loop takes n * O(1) = O(n) time

Collectively, O(n) + O(n) + O(nlogn) = O(nlogn) time

Example unit tests (with pytest)

def test_empty_tree():
    assert Solution().verticalOrder(None) == []


def test_single_node_tree():
    root = TreeNode(1)
    assert Solution().verticalOrder(root) == [[1]]


def test_multi_level_tree():
    """
            1
          /   \
        2      3
      /   \      \
    4      5      6
    """
    node4 = TreeNode(4)
    node5 = TreeNode(5)
    node6 = TreeNode(6)
    node2 = TreeNode(2, node4, node5)
    node3 = TreeNode(3, None, node6)
    root = TreeNode(1, node2, node3)
    assert Solution().verticalOrder(root) == [[4], [2], [1, 5], [3], [6]]