Vertical Order Traversal of a Binary Tree

Updated on 09 July, 2025
Vertical Order Traversal of a Binary Tree header image

Problem Statement

In computational tree theory, vertical order traversal refers to an operation on binary trees where the nodes are visited in a columnar format. Specifically, given a binary tree, we must list the nodes by their columns from left to right. Each node is defined by a coordinate (row, col), where the root node resides at (0, 0). The left child of a node moves one row down and one column to the left (row + 1, col - 1), and the right child moves one row down and one column to the right (row + 1, col + 1).

During the traversal, if multiple nodes occupy the same coordinate, they are to be sorted by their values before listing. The challenge is to calculate and return the vertical order of nodes for each column in the binary tree.

Examples

Example 1

Input:

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

Output:

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

Explanation:

Column -1: Only node 9 is in this column.
Column 0: Nodes 3 and 15 are in this column in that order from top to bottom.
Column 1: Only node 20 is in this column.
Column 2: Only node 7 is in this column.

Example 2

Input:

root = [1,2,3,4,5,6,7]

Output:

[[4],[2],[1,5,6],[3],[7]]

Explanation:

Column -2: Only node 4 is in this column.
Column -1: Only node 2 is in this column.
Column 0: Nodes 1, 5, and 6 are in this column.
1 is at the top, so it comes first.
5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6.
Column 1: Only node 3 is in this column.
Column 2: Only node 7 is in this column.

Example 3

Input:

root = [1,2,3,4,6,5,7]

Output:

[[4],[2],[1,5,6],[3],[7]]

Explanation:

This case is the exact same as example 2, but with nodes 5 and 6 swapped.
Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.

Constraints

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

Approach and Intuition

  1. Tree Traversal:

    • Iterate through the tree nodes using a breadth-first search (BFS), which processes nodes level by level. This ensures nodes are captured in row order.
  2. Tracking Position:

    • As each node is processed, record its (row, col) position. Use a hash map (columnTable) to store nodes according to their col value. If two nodes share the same column, they are added to the same list within that column's key in columnTable.
  3. Sorting Within Columns:

    • For columns with multiple nodes at the same (row, col) coordinate, sort those nodes based on their values. This might require a sorting function within the BFS loop or a post-processing step after all nodes are processed.
  4. Extracting Results:

    • After processing all nodes, extract column keys from columnTable in sorted order. For each key, the associated values give the vertical order for that column.
  5. Putting It All Together:

    • The resultant list of lists is constructed by iterating through the sorted column keys, gathering and formatting the nodes from columnTable according to the problem statement requirements.

Benefits of the Approach

  • Compliance with Constraints: Efficient and within acceptable performance bounds for up to 1000 nodes.
  • Robustness: BFS ensures correct traversal order and avoids skipped nodes.
  • Clarity and Precision: Sorted column processing ensures accurate vertical ordering.

Solutions

  • Java
java
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.
  • Python
python
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.

Comments

No comments yet.