Vertical Sum

Intuition

Nodes on the same vertical line have the same horizontal distance from the root. If we assign root distance 0, then left child is -1 and right child is +1 relative to parent. A DFS can accumulate sums per distance in a map, and a sorted map naturally emits columns from left to right.

Algorithm

1Create a TreeMap<Integer, Integer> map to store column -> sum.
2Run DFS with parameters (node, column).
3At each node, do map[column] += node.data.
4Recurse to left child with column-1.
5Recurse to right child with column+1.
6After DFS, return the TreeMap values in key order as the vertical sums.

Example Walkthrough

Input: Tree: 1 /\ 2 3 / \ 4 5

1.Column -1 has node 2, sum = 2.
2.Column 0 has nodes 1 and 4, sum = 5.
3.Column 1 has node 3, sum = 3.
4.Column 2 has node 5, sum = 5.

Output: [2, 5, 3, 5]

Common Pitfalls

•Use a sorted map (TreeMap) if output order must be left-to-right by column.
•Column updates must be consistent: left decrements, right increments.
•For deep trees, recursion depth can be large; iterative DFS/BFS is an alternative if stack depth is a concern.

Vertical Sum.java

Java


import java.util.*;

class Node {

    int data;
    Node left, right;

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

// Approach: DFS with horizontal distance (column index).
// Add each node value into a TreeMap keyed by column; left child is column-1, right child is column+1.
// TreeMap keeps columns sorted, so values are returned from leftmost to rightmost vertical line.
// Time: O(n log k) Space: O(k + h)

class Solution {

    TreeMap<Integer, Integer> map;

    public ArrayList<Integer> verticalSum(Node root) {
        map = new TreeMap<>();
        calculate(0, root);

        return new ArrayList<>(map.values());
    }

    public void calculate(int level, Node root) {
        if (root == null) {
            return;
        }

        int previousVal = map.getOrDefault(level, 0);
        map.put(level, previousVal + root.data);

        calculate(level - 1, root.left);
        calculate(level + 1, root.right);
    }
}

Was this solution helpful?