Binary Tree Vertical Order Traversal

Naive Solution

A naive approach involves performing a level order traversal of the binary tree and storing the node values along with their column indices in a hash map or dictionary. The column index can be determined by assigning the root node a column index of 0, and then decrementing the column index for left children and incrementing for right children. After the traversal, the hash map can be sorted by column index to retrieve the vertical order traversal.

Algorithm:

1. Perform a level-order traversal of the tree.
2. Maintain a queue to store nodes and their corresponding column indices.
3. For each node:
   • Store the node's value in a hash map, using the column index as the key.
   • Enqueue the left child with a column index of column - 1.
   • Enqueue the right child with a column index of column + 1.
4. Sort the hash map by column index.
5. Return the sorted values as the vertical order traversal.

Optimal Solution

The optimal solution also leverages a level-order traversal with a modification to efficiently keep track of the minimum and maximum column indices encountered during the traversal. This eliminates the need for sorting the entire hash map after the traversal.

Algorithm:

1. Initialize a hash map to store nodes by column index.
2. Initialize min_col and max_col to 0.
3. Perform a level-order traversal using a queue to store pairs of (node, column index).
4. For each node:
   • Update min_col and max_col to reflect the minimum and maximum column indices seen so far.
   • Store the node's value in the hash map at the corresponding column index.
   • Enqueue the left child with a column index of column - 1.
   • Enqueue the right child with a column index of column + 1.
5. Iterate from min_col to max_col and retrieve the values from the hash map for each column index.

Code

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 verticalOrder(root):
    if not root:
        return []

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

    while queue:
        node, col = queue.popleft()
        column_map[col].append(node.val)
        min_col = min(min_col, col)
        max_col = max(max_col, col)

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

    result = []
    for col in range(min_col, max_col + 1):
        result.append(column_map[col])

    return result

Big O Runtime

• Time Complexity: O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the level-order traversal.
• Space Complexity: O(N), where N is the number of nodes in the binary tree. In the worst-case scenario (e.g., a skewed tree), the queue could contain all nodes in the tree. Additionally, the hash map column_map can also store up to N node values.

Edge Cases

• Empty Tree: If the input tree is empty (root is None), the function should return an empty list.
• Single Node Tree: If the tree contains only one node, the function should return a list containing only that node's value.
• Skewed Tree: The algorithm should handle skewed trees correctly, where all nodes are either only left or only right children.
• Duplicate Values: The algorithm should correctly handle trees with duplicate node values.