Binary Tree Vertical Order Traversal

XXX. Vertical Order Traversal of a Binary Tree

Breadth-First Search

Sorting

Problem Statement:

Given the root of a binary tree, perform a vertical order traversal. For each vertical level:

• Sort nodes by their depth. If nodes have the same depth, sort them by their value.
• Return the vertical order traversal as a list of lists.

Algorithm:

The algorithm combines Breadth-First Search (BFS) with sorting to achieve the vertical traversal:

1. Use a custom Pair class to store nodes along with their horizontal (x) and depth (y) coordinates.
2. Perform a BFS, adding each node to a map keyed by its x-coordinate. Track the minimum and maximum x-coordinates.
3. Sort the nodes within each x-coordinate based on depth (y) and value.
4. Collect the sorted values for each x-coordinate into the final result list.

Complexity:

Time Complexity: O(n log n), where n is the number of nodes in the tree. Sorting within each vertical level dominates the complexity.
Space Complexity: O(n), for the map and BFS queue.

Java Implementation:

import java.util.*;

class Solution {

    class Pair {
        TreeNode node;
        int x;  // Horizontal position
        int y;  // Depth

        Pair(TreeNode n, int x, int y) {
            node = n;
            this.x = x;
            this.y = y;
        }
    }

    public List> verticalTraversal(TreeNode root) {
        List> lists = new ArrayList<>(); // Final result list
        Map> map = new HashMap<>(); // Map x -> list of pairs

        Queue q = new LinkedList<>();
        q.add(new Pair(root, 0, 0));

        int min = 0, max = 0; // Track the range of x-coordinates

        // BFS to populate the map
        while (!q.isEmpty()) {
            Pair p = q.remove();

            min = Math.min(min, p.x);
            max = Math.max(max, p.x);

            map.putIfAbsent(p.x, new ArrayList<>());
            map.get(p.x).add(p);

            if (p.node.left != null) q.add(new Pair(p.node.left, p.x - 1, p.y + 1));
            if (p.node.right != null) q.add(new Pair(p.node.right, p.x + 1, p.y + 1));
        }

        // Collect and sort the nodes for each x-coordinate
        for (int i = min; i <= max; i++) {
            List pairs = map.get(i);

            // Sort by depth, and by value if depths are the same
            Collections.sort(pairs, (a, b) -> {
                if (a.y == b.y) return a.node.val - b.node.val;
                return a.y - b.y;
            });

            List level = new ArrayList<>();
            for (Pair p : pairs) level.add(p.node.val);

            lists.add(level);
        }

        return lists;
    }
}

Explanation:

The algorithm performs a BFS traversal while tracking the horizontal (x) and vertical (y) positions of each node. Nodes are grouped by their x-coordinates in a map. After BFS completes, nodes within each x-coordinate are sorted based on depth and value.

• BFS ensures: Nodes at the same depth are visited in order.
• Sorting ensures: Nodes at the same depth and x-coordinate are ordered by value.
• Result list: The sorted nodes for each x-coordinate are added to the final list in ascending x-order.