Vertical Tree Traversal

JavaView on GFG

Problem Overview

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

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?