Binary Tree Vertical Order Traversal - Leetcode Solution

Problem Statement:

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, 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.

Example:

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

 3
/ \

9 20 /
15 7

Output:

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

Explanation:

9 is in the leftmost column. 3 and 15 are in the same column but 3 is at the top. 20 is in the middle of the column and 7 is at the rightmost column.

Solution:

To solve this problem, we will use the BFS approach. We will use a queue to maintain the nodes and keep updating their vertical order by using a hashmap. We will traverse the tree, and for each node, we will store its column value in the map as key and its value in the list of nodes at that column as a value.

Steps:

1. Create an empty hash map to store the column-wise nodes of the binary tree.

2. Create a queue to perform the BFS traversal of the tree.

3. Push the root node into the queue along with its column value, set to 0.

4. Start the BFS traversal of the tree, popping the nodes one by one from the queue till it becomes empty.

5. For every popped node, get its column value from the queue. If the column value does not exist in the hashmap, add it with an empty list as a value.

6. Append the node's value to the list of nodes at that column value in the hashmap.

7. Enqueue the left child of the current node, along with its column value, which is 1 less than the current node's column value, if it exists.

8. Enqueue the right child of the current node, along with its column value, which is 1 more than the current node's column value, if it exists.

9. Traverse the hashmap and extract the list of nodes at each column, from the smallest to the largest column value.

10. Append the list of nodes to the final list to get the vertical order traversal.

Pseudo Code:

def verticalTraversal(root):
    
    # Create a hashmap to store the column wise nodes
    map = {}
    
    # Create a queue to perform BFS of the tree
    queue = []
    
    # Push the root node with its column value as 0
    queue.append((root,0))
    
    # Start BFS traversal of the tree
    while queue:
        node, col = queue.pop(0)
        
        # If column value not in hashmap, add it with an empty list as value
        if col not in map:
            map[col] = []
        
        # Append the node's value to the list of nodes at that column value in the hashmap
        map[col].append(node.val)
        
        # Enqueue the left child if it exists, with its column value as 1 less than current node's column value
        if node.left:
            queue.append((node.left, col-1))
            
        # Enqueue the right child if it exists, with its column value as 1 more than current node's column value
        if node.right:
            queue.append((node.right, col+1))
            
    # Extract list of nodes at each column from the hashmap, from the smallest to the largest column value
    columns = sorted(map.keys())
    res = []
    for col in columns:
        res.append(map[col])
    
    # Return the vertical order traversal
    return res
    

Time Complexity:

The time complexity of this solution is O(n log n) where n is the number of nodes in the binary tree. The reason behind this complexity is because of sorting the keys of the hashmap in the end. OrderedDict can help with this issue.

Space Complexity:

The space complexity of this solution is O(n) because we are using a hashmap to store the nodes of the binary tree in a column-wise manner and a queue for BFS traversal.

1