Vertical Sum in a Binary Search Tree: Algorithm and Code

Vertical sum of a BST means this: assign each node a horizontal distance (HD), then sum every node that shares the same HD.

The root gets HD 0. Every left child is HD minus 1 relative to its parent; every right child is HD plus 1. Nodes in the same vertical column share an HD. Add them up, sort by HD, and the output gives the vertical sum for each column, left to right.

What Vertical Sum Means in a BST

A binary search tree stores keys so that every left-subtree value is smaller than the parent and every right-subtree value is larger. Vertical sum ignores that ordering property entirely. It asks a different question: which nodes fall along the same vertical line when you draw the tree top-down on paper?

The answer depends on horizontal distance. Assign HD 0 to the root. Each time a traversal step moves left, decrement HD by 1. Each time it moves right, increment HD by 1. Every node ends up with an HD value that corresponds to its visual column in the tree diagram. Two nodes at completely different depths can share the same HD if one is reached by repeated right moves and the other by a combination of left and right moves that cancel out.

That is the key insight: HD is not about level or depth; it is about the net lateral displacement from the root.

Once every node has an HD, the vertical sum problem reduces to a grouping problem: accumulate node values per HD key, then output the sums in sorted HD order.

Algorithm: DFS and a Sorted Hashmap

The standard approach uses a depth-first search with a hashmap as the accumulator:

1. Start at the root with hd = 0.
2. Add the current node’s value to column_sums[hd].
3. Recurse to the left child with hd - 1.
4. Recurse to the right child with hd + 1.
5. After the DFS completes, iterate over the hashmap keys in ascending order and print each sum.

The hashmap handles all the grouping automatically. Python’s defaultdict(int) treats missing keys as 0, so no manual initialisation is needed. C++‘s std::map<int, int> keeps keys sorted, so iteration already produces left-to-right output.

The older doubly-linked-list approach described in the GeeksforGeeks vertical sum article achieves the same result by walking a linked list in parallel with the tree traversal, but the bookkeeping is substantially more complex. The hashmap version is cleaner, easier to debug, and just as efficient.

Worked Example: Step Through the 7-Node Tree

Consider this BST:

        10
       /  \
      8    12
     / \  /  \
    4   9 11  14

Running a DFS from the root, with HD starting at 0:

• Node 10 (root), HD 0: column_sums[0] = 10
• Node 8 (left of 10), HD -1: column_sums[-1] = 8
• Node 4 (left of 8), HD -2: column_sums[-2] = 4
• Node 9 (right of 8), HD 0: column_sums[0] = 10 + 9 = 19
• Node 12 (right of 10), HD 1: column_sums[1] = 12
• Node 11 (left of 12), HD 0: column_sums[0] = 19 + 11 = 30
• Node 14 (right of 12), HD 2: column_sums[2] = 14

Sorting by HD and reading the sums:

Horizontal Distance	Nodes	Column Sum
-2	4	4
-1	8	8
0	10, 9, 11	30
1	12	12
2	14	14

HD 0 accumulates three nodes. Node 9 is one right-step from node 8, which is one left-step from the root (net HD = 0). Node 11 is one left-step from node 12, which is one right-step from the root (net HD = 0 as well). Both join the root column.

Code in Python and C++

Python

from collections import defaultdict

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def vertical_sum(root):
    col = defaultdict(int)

    def dfs(node, hd):
        if node is None:
            return
        col[hd] += node.val
        dfs(node.left, hd - 1)
        dfs(node.right, hd + 1)

    dfs(root, 0)
    return [col[k] for k in sorted(col)]

# Build the example tree
root = Node(10)
root.left = Node(8)
root.right = Node(12)
root.left.left = Node(4)
root.left.right = Node(9)
root.right.left = Node(11)
root.right.right = Node(14)

print(vertical_sum(root))  # Output: [4, 8, 30, 12, 14]

defaultdict(int) initialises missing HD keys to 0, so the accumulation line col[hd] += node.val works without any prior check. Sorting the dict keys at the end gives left-to-right column order.

C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

void dfsHelper(Node* root, int hd, map<int, int>& col) {
    if (!root) return;
    col[hd] += root->key;
    dfsHelper(root->left, hd - 1, col);
    dfsHelper(root->right, hd + 1, col);
}

void verticalSum(Node* root) {
    map<int, int> col;
    dfsHelper(root, 0, col);
    for (auto& [hd, sum] : col)
        cout << "HD " << hd << ": " << sum << "\n";
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(8);
    root->right = new Node(12);
    root->left->left = new Node(4);
    root->left->right = new Node(9);
    root->right->left = new Node(11);
    root->right->right = new Node(14);
    verticalSum(root);
    return 0;
}

std::map<int, int> sorts keys in ascending order by default, so no explicit sort step is needed before printing. The structured binding auto& [hd, sum] requires C++17 or later.

Time and Space Complexity

Breaking the complexity down by operation:

• DFS traversal: visits every node exactly once, so O(n) regardless of tree shape.
• Map insertions: each insertion into a std::map or a Python sorted structure costs O(log n) in the worst case, contributing O(n log n) total.
• Final output: iterating over k unique HD values (where k is at most n) costs O(k), which is O(n).

Overall time complexity is O(n log n). If you use an unordered hashmap instead of a sorted map, insertions drop to O(1) amortised, but you still pay O(k log k) at the end to sort the unique HD keys before output. The asymptotic result stays O(n log n).

Space complexity is O(n). The hashmap holds at most n entries. The recursion stack depth equals the height of the tree: O(log n) for a balanced BST and O(n) in the worst case for a skewed (degenerate) tree where every node has only one child.

For a broader look at how recursion stack depth and auxiliary data structures contribute to algorithm space budgets, see Space Complexity of Algorithms with Examples.

Related Patterns: Bottom View, Top View, Vertical Order

Vertical sum is one of three classic column-based tree problems. All three share the same HD-assignment skeleton:

• Vertical order traversal lists all nodes column by column, with ties broken by depth and then by node value. LeetCode 987 is the canonical form of this variant.
• Bottom view prints the last node visible from below in each column — the node with the greatest depth at each HD. When two nodes share HD and depth, the rightmost wins.
• Top view prints the first node visible from above — the node with the smallest depth at each HD.

Once the DFS-plus-map pattern is clear, adapting it to any of the three is a matter of changing what you store per HD key: a sum, a node list, or a depth-filtered node.

The same decompose-then-aggregate thinking appears in the Equilibrium Index of an Array problem: prefix sums from the left, suffix sums from the right, then a scan to find where they balance. Different data structure, same pattern of splitting a computation into independent accumulators.

The hashmap-plus-DFS structure from this article (assign a key, accumulate per key, then sort and output) also appears in how certain ML pipelines pool intermediate representations across attention heads. If you are past the DSA sprint and want to experiment with how language models process and aggregate token-level information, TinkerLLM (₹299 for the first month) runs those experiments without a GPU setup or a research-lab subscription.