Vertical Order Traversal

Solutions

Breadth-First Search (BFS)

Time: O(N)Space: O(N)

We use a queue to perform a breadth-first search (BFS) traversal of the tree. For each node, we also keep track of its column number. We use a map to store the nodes at each column. Finally, we construct the result by iterating over the columns in order.

import java.util.*;


public
class Solution {
  
  
  public List<List<Integer>> verticalTraversal(TreeNode root) {
    
    Map<Integer, List<Integer>> columnTable = new HashMap<>();
    
    int min_column = 0, max_column = 0;
    
    Queue<TreeNode> queue = new LinkedList<>();
    
    Queue<Integer> columnQueue = new LinkedList<>();
    
    queue.offer(root);
    
    columnQueue.offer(0);
    
    while (!queue.isEmpty()) {
      
      TreeNode node = queue.poll();
      
      int column = columnQueue.poll();
      
      if (node != null) {
        
        if (!columnTable.containsKey(column)) columnTable.put(column, new ArrayList<>());
        
        columnTable.get(column).add(node.val);
        
        min_column = Math.min(min_column, column);
        
        max_column = Math.max(max_column, column);
        
        queue.offer(node.left);
        
        columnQueue.offer(column - 1);
        
        queue.offer(node.right);
        
        columnQueue.offer(column + 1);
        
      }
      
    }
    
    List<List<Integer>> result = new ArrayList<>();
    
    for (int i = min_column;
    i <= max_column;
    i++) {
      
      result.add(columnTable.get(i));
      
    }
    
    return result;
    
  }
  
}

Constraints:

Examples:

Solutions

Breadth-First Search (BFS)

Follow-up: