Vertical Order Traversal of a Binary Tree | Leetcode 987 | BFS + Sorting Solution

The Vertical Order Traversal of a Binary Tree problem asks us to traverse a binary tree in a special way:

• Nodes are grouped by their column index (x-coordinate).
• Within the same column, nodes are ordered by row index (y-coordinate).
• If multiple nodes share the same (x, y), sort them by their values.

We must return a list of lists, where each inner list represents a vertical column of the tree.

Here’s the [Problem Link] to begin with.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
- Column -1 → [9]
- Column 0  → [3,15]
- Column 1  → [20]
- Column 2  → [7]

Example 2

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

Intuition and Approach

To solve this problem, we map each node to a coordinate system:

• The root node starts at position (x=0, y=0).
• For left child, move to (x-1, y+1).
• For right child, move to (x+1, y+1).

This way:

• x defines the vertical column index.
• y defines the row level.

Step-by-step approach:

1. BFS Traversal:
   • Use a queue to traverse level by level.
   • For each node, store its (x, y) coordinates.
2. Group Nodes by Coordinates:
   • Use a dictionary nodes_map[x][y] to store all nodes that appear at (x, y).
3. Sorting:
   • Sort by x (columns left to right).
   • For each column, sort by y (top to bottom).
   • If multiple nodes share the same (x, y), sort them by node value.
4. Build Result:
   • Combine values in order to create the vertical traversal list.

Code Implementation

from collections import deque
from typing import Optional, List

# 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]]:
        if not root:
            return []

        # nodes_map[x][y] -> list of node values at coordinate (x, y)
        nodes_map = {}  # dict[int, dict[int, list[int]]]

        # BFS: store (node, x, y)
        q = deque([(root, 0, 0)])

        while q:
            node, x, y = q.popleft()

            # Ensure x key exists
            if x not in nodes_map:
                nodes_map[x] = {}
            # Ensure y key exists for this x
            if y not in nodes_map[x]:
                nodes_map[x][y] = []
            nodes_map[x][y].append(node.val)

            if node.left:
                q.append((node.left, x - 1, y + 1))
            if node.right:
                q.append((node.right, x + 1, y + 1))

        # Build result: sort columns by x, rows by y, and values within same (x,y)
        result = []
        for x in sorted(nodes_map.keys()):
            column = []
            for y in sorted(nodes_map[x].keys()):
                column.extend(sorted(nodes_map[x][y]))
            result.append(column)

        return result

Code Explanation

• nodes_map: Nested dictionary to group nodes by (x, y).
• BFS ensures we visit nodes level by level.
• Left child goes to (x-1, y+1), right child to (x+1, y+1).
• Sorting ensures correct ordering of columns, rows, and values.
• Finally, we merge values into lists for each vertical column.

Dry Run

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

1. Start (3, x=0, y=0) → store at nodes_map[0][0] = [3].
2. Left (9, x=-1, y=1) → nodes_map[-1][1] = [9].
3. Right (20, x=1, y=1) → nodes_map[1][1] = [20].
4. Left of 20 (15, x=0, y=2) → nodes_map[0][2] = [15].
5. Right of 20 (7, x=2, y=2) → nodes_map[2][2] = [7].

Final sorted traversal:

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

Time and Space Complexity

• Time Complexity:
  • BFS traversal: O(N)
  • Sorting: O(N log N) (columns + rows + values)
  • Total: O(N log N)
• Space Complexity:
  • Storing all nodes in nodes_map: O(N)
  • Queue for BFS: O(N)
  • Total: O(N)

Conclusion

The Vertical Order Traversal of a Binary Tree problem can be solved efficiently using BFS with coordinate mapping.

• Assign coordinates (x, y) to nodes.
• Use a nested dictionary to group nodes.
• Sort by column, row, and value to ensure correct ordering.

This approach ensures correctness and efficiency, running in O(N log N) time with O(N) space.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.