Vertical Order Traversal of a Binary Tree

class VerticalOrderTraversal {
    Map<Integer, ArrayList<Pair<Integer, Integer>>> colTable = new HashMap<>();
    int minimumCol = 0, maximumCol = 0;
    
    private void traverse(TreeNode node, Integer depth, Integer horizontalDist) {
        if (node == null)
            return;
    
        if (!colTable.containsKey(horizontalDist)) {
            this.colTable.put(horizontalDist, new ArrayList<Pair<Integer, Integer>>());
        }
    
        this.colTable.get(horizontalDist).add(new Pair<Integer, Integer>(depth, node.val));
        this.minimumCol = Math.min(minimumCol, horizontalDist);
        this.maximumCol = Math.max(maximumCol, horizontalDist);
        // Execute DFS traversal in preorder
        this.traverse(node.left, depth + 1, horizontalDist - 1);
        this.traverse(node.right, depth + 1, horizontalDist + 1);
    }
    
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
    
        // 1). Conduct the DFS traversal
        this.traverse(root, 0, 0);
    
        // 2). Extract and sort results from the column table
        for (int i = minimumCol; i <= maximumCol; ++i) {
            // Sort by row and value
            Collections.sort(colTable.get(i), new Comparator<Pair<Integer, Integer>>() {
                @Override
                public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) {
                    if (p1.getKey().equals(p2.getKey()))
                        return p1.getValue() - p2.getValue();
                    else
                        return p1.getKey() - p2.getKey();
                }
            });
    
            List<Integer> sortedCol = new ArrayList<>();
            for (Pair<Integer, Integer> p : colTable.get(i)) {
                sortedCol.add(p.getValue());
            }
            result.add(sortedCol);
        }
    
        return result;
    }
}

The Java implementation provided performs a vertical order traversal of a binary tree. Here is a summary of how it works:

• A Map<Integer, ArrayList<Pair<Integer, Integer>>> named colTable stores nodes against their respective horizontal distances. Each node is represented by a pair containing the depth and its value.
• The traverse method performs a Depth First Search (DFS) on the tree:
  • It checks if the current node is null, if so, it returns.
  • Nodes are stored in colTable with their depth and value.
  • Recursive calls adjust the horizontal distance, moving left (decrementing) and right (incrementing).
• Minimum and maximum columns (minimumCol and maximumCol) are updated during traversal to keep track of the leftmost and rightmost tree boundaries.
• The verticalOrder method processes the tree:
  • Begins with checking if the root is null. If true, returns an empty result.
  • Calls traverse to fill colTable.
  • Processes entries from minimumCol to maximumCol, sorting them by depth and value when depths are the same.
  • The sorted values for each column are aggregated into result.

Following these steps ensures that each vertical column from left to right is sorted first by the depth of nodes and then by their values if multiple nodes share the same depth.

Key insights:

• Utilizes DFS and a hashmap with a list to manage sorting and output.
• Ensures accuracy in vertical arrangements by careful tracking and sorting mechanisms.
• Efficiently handles null trees and provides a structured output format.

class Solution:
    def verticalOrder(self, rootNode: TreeNode) -> List[List[int]]:
        if rootNode is None:
            return []
    
        # Dict to maintain column-wise nodes
        colTable = defaultdict(list)
        # Initialize column limits
        min_col = max_col = 0
    
        def traverse(node, vertical, horizontal):
            if node:
                nonlocal min_col, max_col
                colTable[horizontal].append((vertical, node.val))
                min_col = min(min_col, horizontal)
                max_col = max(max_col, horizontal)
    
                # Recursive traversals for left and right children
                traverse(node.left, vertical + 1, horizontal - 1)
                traverse(node.right, vertical + 1, horizontal + 1)
    
        # Start DFS traversal from the root
        traverse(rootNode, 0, 0)
    
        # Prepare output list from the colTable
        result = []
        for column in range(min_col, max_col + 1):
            # Sorting the tuples by their row index and then by value
            result.append([value for row, value in sorted(colTable[column])])
    
        return result

This solution outlines a method to perform vertical order traversal on a binary tree using Python 3.

• The input node is checked to ensure it is not None. If it's None, the function returns an empty list.
• A dictionary called colTable is initialized using defaultdict of the list type to keep track of nodes categorized by their "horizontal distance" from the root.
• Two variables, min_col and max_col, are initialized to 0. They are used to track the smallest and largest horizontal distances that have been encountered in the tree, respectively.
• The traverse function is a nested function defined to perform a Depth First Search (DFS) traversal of the tree. It accepts:
  • node: current tree node.
  • vertical: vertical level of the node.
  • horizontal: horizontal distance of the node from the root.
• In the traverse function:
  • If the current node exists, the node value and its vertical level are appended to the list in colTable that corresponds to its horizontal distance.
  • Updates are made to min_col and max_col based on the current node's horizontal position.
  • The function then recursively calls itself for the left and right children of the current node, adjusting the vertical and horizontal values as appropriate.

After the traversal completes, the outputs are collected from colTable. The results are sorted and appended to the final list result:

• The result list is constructed by iterating from min_col to max_col.
• For each column, values are sorted, first by row index (vertical) and then by node value to maintain the order of nodes as observed in vertical traversal from top to bottom.

This ensures that the final output result represents the node values in vertical order, where each sublist corresponds to nodes at the same horizontal distance, sorted vertically.