#987

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Vertical Order Traversal of a Binary Tree

Perform a vertical order traversal of a binary tree, sorting nodes by their values within columns.

hash table tree depth first search breadth first search sorting

Problem Statement

Given the root of a binary tree, your task is to calculate its vertical order traversal. For each node, you need to determine its position in terms of column and row. The root node starts at position (0, 0), and the left child of a node at (row, col) will be at (row + 1, col - 1), while the right child will be at (row + 1, col + 1).

The vertical order traversal must return a list of column-wise nodes, ordered from the leftmost column to the rightmost. Nodes in the same column and row should be sorted by their values, and if there are multiple nodes with the same coordinates, they must be sorted in increasing order of their value.

Examples

Example 1

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

Output: [[9],[3,15],[20],[7]]

Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.

Example 2

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

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

Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column. 1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.

Example 3

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

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

This case is the exact same as example 2, but with nodes 5 and 6 swapped. Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints

The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 1000

Solution Approach

Breadth-First Search (BFS) with Hash Table

In this approach, use a BFS traversal, starting from the root node. Use a hash table to store nodes by their column index and row position. Ensure to add nodes in the correct order and sort them by their row number and value when necessary.

Depth-First Search (DFS) with Column Tracking

This solution uses DFS while keeping track of the column indices as you traverse. For each node, calculate its vertical position relative to the root and store nodes in a hash table indexed by their column positions. After traversal, sort the nodes by row and value.

Sorting After Traversal

Once all nodes are collected in the hash table, sort them by their column index. Within each column, sort nodes by their row index and then by their value. Finally, return the list of nodes column by column.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal method chosen: BFS or DFS. For both, the time complexity is O(N log N), where N is the number of nodes, due to sorting operations within each column. The space complexity is O(N) due to the storage required for the nodes and their respective columns in the hash table.

What Interviewers Usually Probe

Evaluate the candidate's ability to apply tree traversal algorithms like BFS and DFS.
Look for understanding of hash table usage for vertical column grouping.
Assess how the candidate handles sorting operations within the columns.

Common Pitfalls or Variants

Common pitfalls

Confusing node positioning, such as incorrectly calculating the column and row positions.
Failure to account for sorting nodes within the same column and row based on their values.
Inefficient use of data structures, leading to unnecessary complexity.

Follow-up variants

What if the tree has only one node? The output should still be a list containing a single node in its own column.
Can we optimize for larger trees? Consider methods that reduce sorting overhead for large datasets.
How would the solution change if nodes were added dynamically, requiring frequent updates to the tree structure?

FAQ

What is vertical order traversal in a binary tree?

Vertical order traversal lists nodes column by column, starting from the leftmost column, ordered top to bottom within each column.

How do you handle nodes at the same row and column?

Nodes in the same row and column are sorted by their values, ensuring that smaller values come before larger ones in the result.

Which algorithm is most commonly used for this problem?

Both BFS and DFS are commonly used to traverse the tree, with BFS being more straightforward for this problem due to its level-wise exploration.

What data structure is best for tracking node positions?

A hash table is ideal for storing nodes by their column index, ensuring easy retrieval and sorting of nodes based on their vertical and horizontal positions.

What is the time complexity of the vertical order traversal?

The time complexity is O(N log N), where N is the number of nodes, due to the sorting step for nodes within each column.

terminal

Solution

Solution 1: DFS + Sorting

We design a function $dfs(root, i, j)$, where $i$ and $j$ represent the row and column of the current node. We can record the row and column information of the nodes through depth-first search, store it in an array or list $nodes$, and then sort $nodes$ in the order of column, row, and value.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

# 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 verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        def dfs(root: Optional[TreeNode], i: int, j: int):
            if root is None:
                return
            nodes.append((j, i, root.val))
            dfs(root.left, i + 1, j - 1)
            dfs(root.right, i + 1, j + 1)

        nodes = []
        dfs(root, 0, 0)
        nodes.sort()
        ans = []
        prev = -2000
        for j, _, val in nodes:
            if prev != j:
                ans.append([])
                prev = j
            ans[-1].append(val)
        return ans

Continue Practicing

#865 smallest subtree with all the deepest nodes #863 all nodes distance k in binary tree #1123 lowest common ancestor of deepest leaves