Practice/Meta/Leetcode 314. Binary Tree Vertical Order Traversal

Leetcode 314. Binary Tree Vertical Order Traversal

CodingMust

Problem

You are given the root of a binary tree. Your task is to perform a column-by-column traversal and return the values of all nodes grouped by their vertical position.

Imagine drawing a vertical line through the root node (column 0). Moving to a left child decreases the column index by 1, while moving to a right child increases it by 1. Return a list where each element contains all node values in that column, ordered from the leftmost column to the rightmost column.

Within each column, nodes should appear in the order they would be visited during a level-order (top-to-bottom) traversal. If multiple nodes exist at the same position (same column and level), they should appear in left-to-right order as encountered during the traversal.

Requirements

1. Group all tree nodes by their column index (horizontal distance from root)
2. Return columns sorted from leftmost to rightmost
3. Within each column, maintain top-to-bottom ordering
4. For nodes at the same column and same level, preserve left-to-right ordering
5. Handle empty trees by returning an empty list

Constraints

• The number of nodes in the tree is in the range [0, 100]
• -100 ≤ Node.val ≤ 100
• Column indices can range from negative to positive values
• Expected time complexity: O(n) where n is the number of nodes
• Expected space complexity: O(n) for storing the result and auxiliary data structures

Examples

Example 1:

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

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

• Column -1: node 9
• Column 0: nodes 3 and 15 (15 is below 3)
• Column 1: node 20
• Column 2: node 7 `

Example 2:

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

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

• Column -2: node 4
• Column -1: node 2
• Column 0: nodes 1, 5, 6 (all at different or same levels, visited left-to-right)
• Column 1: node 3
• Column 2: node 7 `

Example 3:

Input: root = [] Output: [] Explanation: Empty tree has no columns