Vertical Tree Traversal

JavaView on GFG

Intuition

Print binary tree nodes column by column, top to bottom within each column.

Algorithm

1BFS/DFS with (node, col, row) tracking. Group by column. Within column sort by row, then value.

Common Pitfalls

•Same as LC 987. Use TreeMap of column -> sorted list. Sort by (row, value) within each column.

Vertical Tree Traversal.java

Java

// Approach: BFS/DFS tracking horizontal distance. Group nodes by HD, sort within each group by level then value.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left;
    Node right;

    Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class Solution {
    class pair {
        int dis;
        Node node;

        pair(int dis, Node node) {
            this.dis = dis;
            this.node = node;
        }
    }

    public ArrayList<ArrayList<Integer>> verticalOrder(Node root) {
        // code here
        var ans = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return ans;

        Queue<pair> q = new ArrayDeque<>();
        var mp = new TreeMap<Integer, ArrayList<Integer>>();

        q.offer(new pair(0, root));
        while (!q.isEmpty()) {
            pair p = q.poll();
            int d = p.dis;
            Node node = p.node;

            mp.computeIfAbsent(d, k -> new ArrayList<Integer>()).add(node.data);

            if (node.left != null)
                q.offer(new pair(d - 1, node.left));
            if (node.right != null)
                q.offer(new pair(d + 1, node.right));
        }

        for (var l : mp.values())
            ans.add(l);

        return ans;
    }
}

Was this solution helpful?