Vertical Order Traversal of a Binary Tree

Problem Description

Given the root of a binary tree, the task is to calculate the vertical order traversal of the binary tree. For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0). The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index, starting from the leftmost column and ending on the rightmost column. If there are multiple nodes in the same row and same column, sort these nodes by their values.

Naive Approach

A naive approach would involve performing a tree traversal (e.g., Breadth-First Search) to identify the column index for each node. Store the nodes along with their column indices in a suitable data structure (e.g., a hash map where keys are column indices, and values are lists of node values). After the traversal, sort the nodes within each column by their row and then by their values if they are at the same position. Finally, collect the nodes column by column from left to right.

Complexity Analysis:

• Time Complexity: O(N log N), where N is the number of nodes in the tree. This complexity arises primarily from the sorting step within each column.
• Space Complexity: O(N), as we need to store nodes and their column indices.

Optimal Approach

A more optimized approach can reduce the sorting complexity. We use a modified Breadth-First Search (BFS) to traverse the tree. During the traversal, we keep track of the column index for each node. Instead of directly sorting the nodes in each column, we store the nodes in a list along with their row and column indices. Once BFS is complete, sort the list based on column index, row index, and value. After sorting, group the nodes by their column indices to generate the final vertical order traversal.

Algorithm:

1. Start a BFS traversal from the root node with column index 0 and row index 0.
2. For each node visited, store its value, row index, and column index.
3. After the BFS traversal, sort the collected nodes based on the column index, row index, and value. The sorting is done to ensure the nodes are correctly ordered as specified in the problem.
4. Group the sorted nodes by their column indices and form the vertical order traversal list.

Code Implementation (Python):

from collections import defaultdict, deque

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


def verticalTraversal(root):
    if not root:
        return []

    nodes = []
    queue = deque([(root, 0, 0)])  # (node, row, col)

    while queue:
        node, row, col = queue.popleft()
        nodes.append((col, row, node.val))

        if node.left:
            queue.append((node.left, row + 1, col - 1))
        if node.right:
            queue.append((node.right, row + 1, col + 1))

    nodes.sort()

    result = []
    current_col = float('-inf')
    current_list = []

    for col, row, val in nodes:
        if col != current_col:
            if current_list:
                result.append(current_list)
            current_col = col
            current_list = [val]
        else:
            current_list.append(val)

    if current_list:
        result.append(current_list)

    return result

Complexity Analysis:

• Time Complexity: O(N log N), where N is the number of nodes in the tree. This complexity is dominated by the sorting step after the BFS traversal.
• Space Complexity: O(N), as we need to store nodes, row indices, and column indices.

Edge Cases:

1. Empty Tree: If the root is None, return an empty list.
2. Single Node Tree: If the tree contains only the root node, return a list containing a list with the root node's value.
3. Skewed Trees: The algorithm should handle skewed trees gracefully, whether left-skewed or right-skewed.
4. Nodes at the Same Position: The algorithm correctly sorts nodes at the same position by their values.

By following this optimized approach, the vertical order traversal of the binary tree can be determined efficiently while adhering to the given constraints and edge cases.