Binary Tree Vertical Order Traversal

Tested Python solution for LeetCode 314 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 314, Medium. Topics: Tree, Depth-First Search, Breadth-First Search, Hash Table, Binary Tree, Sorting. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 314   # by problem number
lcpy gen -s binary_tree_vertical_order_traversal   # by problem name

​

Problem

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.

​

Examples

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

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

Input: root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]
Output: [[4],[2,5],[1,10,9,6],[3],[11]]

​

Constraints

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n) — BFS visit plus one pass over the column span
    # Space: O(n) — queue and column buckets
    def vertical_order(self, root: TreeNode[int] | None) -> list[list[int]]:
        if root is None:
            return []

        columns: dict[int, list[int]] = {}
        queue: deque[tuple[TreeNode[int], int]] = deque([(root, 0)])
        min_col = max_col = 0
        while queue:
            node, col = queue.popleft()
            columns.setdefault(col, []).append(node.val)
            min_col = min(min_col, col)
            max_col = max(max_col, col)
            if node.left is not None:
                queue.append((node.left, col - 1))
            if node.right is not None:
                queue.append((node.right, col + 1))

        return [columns[col] for col in range(min_col, max_col + 1)]

​

Complexity

Time	Space
O(n) — BFS visit plus one pass over the column span	O(n) — queue and column buckets

​

Tags

NeetCode All.