Introduction

The vertical sum of a binary tree is the sum of node values that fall on the same vertical line when the tree is drawn with the root at horizontal distance 0. It is a useful interview problem because it tests tree traversal, coordinate tracking, and map-based aggregation in one small exercise. The key idea is to assign each node a horizontal distance and accumulate values by that distance.

How Vertical Distance Works

Start with the root at horizontal distance 0.

• the left child of a node is at distance parent - 1
• the right child of a node is at distance parent + 1

For this tree:

1        1
2      /   \
3     2     3
4    / \   / \
5   4   5 6   7

The horizontal distances are:

• '4 at -2'
• '2 at -1'
• '1, 5, and 6 at 0'
• '3 at 1'
• '7 at 2'

So the vertical sums are:

• '-2 -> 4'
• '-1 -> 2'
• '0 -> 12'
• '1 -> 3'
• '2 -> 7'

Depth-First Search Solution

A depth-first traversal is the simplest implementation. Carry the current horizontal distance during recursion and update a dictionary.

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def vertical_sum(root):
9    sums = {}
10
11    def dfs(node, hd):
12        if node is None:
13            return
14
15        sums[hd] = sums.get(hd, 0) + node.value
16        dfs(node.left, hd - 1)
17        dfs(node.right, hd + 1)
18
19    dfs(root, 0)
20    return dict(sorted(sums.items()))
21
22
23root = Node(
24    1,
25    Node(2, Node(4), Node(5)),
26    Node(3, Node(6), Node(7)),
27)
28
29print(vertical_sum(root))

Output:

{-2: 4, -1: 2, 0: 12, 1: 3, 2: 7}

This works because each node is visited once, and each visit updates one entry in the map.

Breadth-First Search Solution

Breadth-first search also works well, especially if you prefer iterative tree traversal.

1from collections import deque
2
3
4def vertical_sum_bfs(root):
5    if root is None:
6        return {}
7
8    sums = {}
9    queue = deque([(root, 0)])
10
11    while queue:
12        node, hd = queue.popleft()
13        sums[hd] = sums.get(hd, 0) + node.value
14
15        if node.left:
16            queue.append((node.left, hd - 1))
17        if node.right:
18            queue.append((node.right, hd + 1))
19
20    return dict(sorted(sums.items()))

The DFS and BFS versions have the same asymptotic complexity. The difference is mostly implementation style.

Complexity

Let n be the number of nodes.

• Time complexity: O(n), because every node is processed once.
• Space complexity: O(n) in the worst case for the map and for recursion stack or queue storage.

Sorting the final dictionary by horizontal distance adds O(k log k) where k is the number of distinct vertical lines, but k is at most n.

A Useful Variation

Sometimes interviewers ask for vertical order traversal rather than vertical sum. The setup is the same, but instead of storing a running integer sum, you store a list of values for each horizontal distance.

That is why it helps to separate the coordinate idea from the exact aggregation rule. Once you track horizontal distance correctly, you can compute sums, lists, averages, or maximums with the same traversal pattern.

Common Pitfalls

• Forgetting to decrease the horizontal distance for the left child and increase it for the right child.
• Confusing vertical sum with level-order traversal, which groups by depth instead of horizontal distance.
• Returning the map in arbitrary hash order when the expected answer is left-to-right.
• Using global state carelessly in recursive solutions.
• Missing the empty-tree case and crashing on None input.

Summary

• Vertical sum groups nodes by horizontal distance from the root.
• Assign the root distance 0, left as -1, and right as +1 relative to the parent.
• Use either DFS or BFS and accumulate sums in a dictionary.
• Sort by horizontal distance if you need left-to-right output.
• The core algorithm runs in O(n) time.