Binary Tree Vertical Order Traversal

Problem Statement

In this problem, we are given the root of a binary tree and are required to perform a vertical order traversal of its nodes' values. Vertical order traversal means collecting the values of the tree nodes as they appear vertically, from left to right. If nodes overlap vertically, they should be listed from top to bottom, and if nodes are at the same level within the same column, they should be reported from left to right. Our task is to categorize these values column by column and provide the output in the form of a list of lists, where each sublist represents a column of the tree.

Examples

Example 1

Input:

root = [3,9,20,null,null,15,7]

Output:

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

Example 2

Input:

root = [3,9,8,4,0,1,7]

Output:

[[4],[9],[3,0,1],[8],[7]]

Example 3

Input:

root = [1,2,3,4,10,9,11,null,5,null,null,null,null,null,null,null,6]

Output:

[[4],[2,5],[1,10,9,6],[3],[11]]

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Approach and Intuition

Understanding how to approach the vertical order traversal of a binary tree can be broken down into the following steps:

1. Assign a position to each node. This position will have two components:

   • Horizontal position (or x-coordinate): This changes as we move from left (-1) to right (+1) relative to the root, which has position 0.
   • Vertical position (or y-coordinate): This changes as we move from top (0) to bottom (+1) as we go down each level in the tree.

2. Traverse the binary tree (typically using breadth-first search, BFS) and keep track of each node's coordinates and value. During this traversal:

   • Use a queue to manage nodes to be processed. Begin with the root node, initializing its position as (0,0).
   • For each node processed, capture its value in a data structure, using its x-coordinate as a key and appending its value along with its y-coordinate (to handle sorting later if multiple values fall into the same x-coordinate).
   • For each node, push its left and right children into the queue if they exist, adjusting their horizontal positions accordingly (-1 for left and +1 for right) while increasing the vertical position by 1.

3. Once the traversal is done, sort the collected nodes:

   • First, sort by x-coordinate—that is, the columns.
   • Within each column, sort by y-coordinate to ensure values appear from top to bottom. If two nodes have the same y-coordinate, they should appear from left to right, as they would naturally by the nature of BFS.

4. Convert the sorted structure into the desired output format:

   • Iterate through the sorted keys (x-coordinates) and gather the node values into sublists to create the final list of lists that represents the vertical order traversal.

By understanding these steps, we can effectively process and categorize the binary tree's nodes into their respective vertical columns while adhering to the constraints and properties of binary tree traversal.

Solutions

class Solution {
  // Store nodes values by columns
  Map<Integer, ArrayList<Pair<Integer, Integer>>> nodeStorage = new HashMap<>();
  int minCol = 0, maxCol = 0;
    
  private void runDFS(TreeNode node, Integer depth, Integer col) {
    if (node == null)
      return;
    
    if (!nodeStorage.containsKey(col)) {
      this.nodeStorage.put(col, new ArrayList<>());
    }
    
    this.nodeStorage.get(col).add(new Pair<>(depth, node.val));
    this.minCol = Math.min(minCol, col);
    this.maxCol = Math.max(maxCol, col);
        
    // Recursively call left and right subtree
    this.runDFS(node.left, depth + 1, col - 1);
    this.runDFS(node.right, depth + 1, col + 1);
  }
    
  public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> output = new ArrayList<>();
    if (root == null) {
      return output;
    }
    
    this.runDFS(root, 0, 0);
    
    // Retrieve results ordered by column and sorted by row
    for (int i = minCol; i <= maxCol; ++i) {
    
      Collections.sort(nodeStorage.get(i), new Comparator<Pair<Integer, Integer>>() {
        @Override
        public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
          return p1.getKey() - p2.getKey();
        }
      });
    
      List<Integer> sortedColumn = new ArrayList<>();
      for (Pair<Integer, Integer> p : nodeStorage.get(i)) {
        sortedColumn.add(p.getValue());
      }
      output.add(sortedColumn);
    }
    
    return output;
  }
}