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.

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]]

Vertical Order Traversal Algorithm Explained

The vertical order traversal algorithm is designed to traverse a binary tree and retrieve a list of node values grouped by their vertical columns. The traversal is conducted from top to bottom and left to right within each column. Below is a detailed explanation of the algorithm’s workings.

Key Concepts

Binary Tree Structure

A binary tree consists of nodes, where each node has a maximum of two children referred to as the left and right child. In this algorithm, the tree is represented in terms of nodes with integer values.

Vertical Columns

The tree is viewed from the side, dividing it into vertical columns based on the horizontal position of nodes. Each column is identified by an index, where the root node is at index 0. Nodes to the left are assigned negative indices, and those to the right are assigned positive indices.

Breadth-First Search (BFS)

The algorithm employs a breadth-first search (BFS) method to explore all nodes level by level. This technique is essential for ensuring that nodes in the same row are processed from left to right.

Algorithm Steps

1. Initialize Structures

• Column Map: A map to hold lists of node values for each column. The keys are column indices, and the values are lists of node values.
• Queue: A queue used for BFS traversal. The queue holds pairs of nodes and their corresponding column indices.
• Min and Max Column Indices: Variables to keep track of the smallest and largest column indices encountered during the traversal.

2. Start with the Root Node

• Begin the traversal at the root node, enqueueing the root node along with its column index (0).
• If the root node is null, return an empty list immediately.

3. Process the Queue

While the queue is not empty:

• Dequeue an element to get the current node and its column index.
• Insert the node’s value into the list corresponding to its column index in the column map.
• If there is a left child, enqueue it with the column index decremented by one (col – 1) and update the minimum column index if necessary.
• If there is a right child, enqueue it with the column index incremented by one (col + 1) and update the maximum column index if necessary.

4. Collect the Results

• After processing all nodes, iterate from the minimum column index to the maximum column index.
• Collect the lists of node values from the column map in order, ensuring that the output format meets the requirements (i.e., a list of lists).

5. Return the Result

• Finally, return the compiled list of lists representing the vertical order traversal of the binary tree.

Complexity Analysis

• Time Complexity: O(n), where n is the number of nodes in the binary tree. This is because every node is processed exactly once during the BFS traversal.
• Space Complexity: O(n), which accounts for storing the node values in the column map and the queue used for BFS.

The vertical order traversal algorithm effectively organizes binary tree nodes into their respective vertical columns, ensuring that the order of traversal reflects both vertical and horizontal alignment requirements. The utilization of BFS facilitates systematic exploration and accurate results, making this algorithm robust for varying binary tree structures.

This file provides both Java and Python implementations for performing a vertical order traversal of a binary tree, using a BFS approach to ensure top-down, left-to-right ordering.

Java Implementation

import java.util.*;

public class VerticalOrderJava {
    /**
     * Performs a vertical order traversal using BFS.
     * Time: O(n), Space: O(n)
     */
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        Map<Integer, List<Integer>> columnMap = new HashMap<>();
        Deque<NodeColumn> queue = new ArrayDeque<>();
        queue.offer(new NodeColumn(root, 0));

        int minCol = 0, maxCol = 0;
        while (!queue.isEmpty()) {
            NodeColumn nc = queue.poll();
            TreeNode node = nc.node;
            int col = nc.col;

            columnMap.computeIfAbsent(col, k -> new ArrayList<>()).add(node.val);
            if (node.left != null) {
                queue.offer(new NodeColumn(node.left, col - 1));
                minCol = Math.min(minCol, col - 1);
            }
            if (node.right != null) {
                queue.offer(new NodeColumn(node.right, col + 1));
                maxCol = Math.max(maxCol, col + 1);
            }
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int c = minCol; c <= maxCol; c++) {
            result.add(columnMap.get(c));
        }
        return result;
    }

    private static class NodeColumn {
        final TreeNode node;
        final int col;
        NodeColumn(TreeNode node, int col) {
            this.node = node;
            this.col = col;
        }
    }
}

Explanation:

• Class Definition: VerticalOrderJava defines the method for vertical order traversal of a binary tree.
• Helper Classes: NodeColumn to hold a tree node and its associated column index.
• BFS Approach: A queue is used for BFS traversal, tracking the columns of each node.
• Column Tracking: A Map is used to maintain lists of node values for each column, and a range of columns is tracked to return the results in the correct order.

Python Implementation

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

class TreeNode:
    def __init__(self, val: int = 0,
                 left: 'TreeNode' = None,
                 right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        """
        Performs a vertical order traversal using BFS.
        - Use a queue of (node, column) pairs.
        - Track min and max column indices.
        - Append node values to buckets in a defaultdict(list).
        - Finally, collect buckets from min to max.
        Time Complexity: O(n)
        Space Complexity: O(n)
        """
        if not root:
            return []

        col_map = defaultdict(list)
        queue = deque([(root, 0)])
        min_col = max_col = 0

        while queue:
            node, col = queue.popleft()
            col_map[col].append(node.val)

            if node.left:
                queue.append((node.left, col - 1))
                min_col = min(min_col, col - 1)
            if node.right:
                queue.append((node.right, col + 1))
                max_col = max(max_col, col + 1)

        return [col_map[c] for c in range(min_col, max_col + 1)]

Explanation:

• Class Definition: TreeNode defines the structure of a node in the binary tree; Solution contains the method for vertical order traversal.
• BFS Approach: Similar to the Java implementation, it uses a queue to traverse the tree and a defaultdict to collect node values based on their column index.
• Column Tracking: By using min and max column indices, the function compiles the results in correct order and outputs them as a list of lists.