Binary Tree Vertical Order Traversal

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;
  }
}

The code in discussion offers a solution for performing a vertical order traversal of a binary tree using Java. It utilizes a depth-first search (DFS) strategy along with a hash map to effectively categorize and store tree node values based on their horizontal distances (columns) from the root.

• Begin by setting up a hash map nodeStorage to maintain lists of nodes grouped by their column indexes. Each list contains pairs, with each pair holding a depth and a node value.

• Implement the runDFS method, where for each node, if not already present, a new list for the column in nodeStorage is created. Add the current node along with its depth to the respective column list. Update the minimum and maximum column values.

  • Recursively proceed to the left (column - 1) and right (column + 1) children of the current node, increasing the depth by 1.

• In verticalOrder, initialize the output list of lists. If the root is null, return the empty list directly. Else, start the depth-first traversal from the root node positioned at depth 0, column 0.

  • After populating nodeStorage, iterate through the columns from minCol to maxCol.
  • For each column, sort its list by depth.
  • Extract the node values from sorted pairs and add them to the output.

• Finally, return the output, which contains the node values in the order of their vertical levels from leftmost to rightmost columns.

This method ensures all nodes appearing in a vertical line are processed based on their depth, with top-down order for nodes at the same depth within the same vertical line. This efficient categorization allows for clear, structured output that accurately represents vertical levels in a binary tree.

from collections import defaultdict

class Solution:
    def verticalTraversal(self, node_root: TreeNode) -> List[List[int]]:
        if not node_root:
            return []

        vertical_map = defaultdict(list)
        column_min = column_max = 0

        def traverse(node, depth, columns):
            if node:
                nonlocal column_min, column_max
                vertical_map[columns].append((depth, node.val))
                column_min = min(column_min, columns)
                column_max = max(column_max, columns)

                traverse(node.left, depth + 1, columns - 1)
                traverse(node.right, depth + 1, columns + 1)

        traverse(node_root, 0, 0)

        result = []
        for col in range(column_min, column_max + 1):
            vertical_map[col].sort(key=lambda x: x[0])
            result.append([val for _, val in vertical_map[col]])

        return result

The provided Python code implements a function to perform a vertical order traversal on a binary tree. It sorts tree nodes vertically by columns and horizontally by depth using a depth-first search approach. Follow these steps to understand the implementation:

1. Check if the input node_root is None. If it is, return an empty list early.
2. Use a defaultdict to store nodes based on their column indices, where each key points to a list of tuples containing depth and node values.
3. Initialize column_min and column_max to track the smallest and largest column indices encountered during the traversal.
4. Define an inner recursive function traverse to navigate the tree. This function:
   • Updates column_min and column_max.
   • Recursively calls itself for the left child with columns - 1 and the right child with columns + 1.
5. Initiate the traversal with traverse(node_root, 0, 0).
6. Prepare to output the result by iterating from column_min to column_max.
7. For each column key in vertical_map, sort the list of tuples primarily by depth (ensuring top-down order within the same column).
8. Extract node values from the sorted tuples and store them in the result list.
9. Finally, return the result, which contains lists of values for each vertical column.

This implementation ensures that nodes are returned in the expected vertical column order, sorted by depth, using an efficient combination of depth-first traversal and sorting by depth within columns.