Vertical Sum of Binary Tree — Solution in Python, Java & C++
Vertical Sum of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Vertical Sum of Binary Tree is a medium coding problem on hash table, depth-first search and trees, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Hash Table, Depth-First Search, Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the sum of the node values in each vertical line, from the leftmost line to the rightmost.
The root is on line 0; a node's left child is on the line one to the left (-1) and its right child on the line one to the right (+1).
Example 1
Input: root = [1,2,3,4,5,6,7]
Output: [4,2,12,3,7]
Explanation: Columns −2..2 hold {4}, {2}, {1, 5, 6}, {3}, {7}: sums 4, 2, 12, 3, 7.
Example 2
Input: root = [1,2,3,4,5,null,6]
Output: [4,2,6,3,6]
Explanation: Column 0 holds 1 and 5; column 1 holds 3; column 2 holds 6.
Example 3
Input: root = [9]
Output: [9]
Explanation: One node, one column.
Constraints
1 <= number of nodes <= 10^41 <= Node.val <= 10^5
Hints for Vertical Sum of Binary Tree
Hint 1
Give each node its horizontal distance from the root: root 0, left child − 1, right child + 1.
Hint 2
Any traversal works — accumulate each node's value into the total for its distance.
Hint 3
Distances from the smallest to the largest are contiguous, so after the traversal output the totals in that range.
How to solve Vertical Sum of Binary Tree
Carry the horizontal distance through any traversal and add each value into a per-line total; the lines that occur form a contiguous range, which is output from left to right.
Approach
- Traverse the tree (DFS or BFS) carrying the line number: left child
d - 1, right childd + 1. - Add the node's value to
total[d]and update the smallest and largestdseen. - Return
total[min], …, total[max].
Why it works
Every node is visited once and added to exactly the line it lies on, so each total is its line's sum. The path from the root to the leftmost or rightmost node steps one line at a time, so every line between the extremes is occupied and the output has no gaps.
Complexity
- Time —
O(n) with an offset array (O(n log n) with a sorted map) - Space —
O(n)
Pitfalls
- Line numbers go negative — shift them by the node count before using them as array indices.
- The output runs left to right, not in the order lines were first discovered.
Reference solution
Python
from typing import List, Optional
def verticalSum(root: Optional[TreeNode]) -> List[int]:
total = {}
stack = [(root, 0)] if root else []
while stack:
node, d = stack.pop()
total[d] = total.get(d, 0) + node.val
if node.left:
stack.append((node.left, d - 1))
if node.right:
stack.append((node.right, d + 1))
if not total:
return []
return [total[d] for d in range(min(total), max(total) + 1)]Java
public static int[] verticalSum(TreeNode root) {
if (root == null) return new int[0];
TreeMap<Integer, Integer> total = new TreeMap<>();
addColumns(root, 0, total);
int[] out = new int[total.size()];
int i = 0;
for (int v : total.values()) out[i++] = v;
return out;
}
static void addColumns(TreeNode node, int d, TreeMap<Integer, Integer> total) {
if (node == null) return;
total.merge(d, node.val, Integer::sum);
addColumns(node.left, d - 1, total);
addColumns(node.right, d + 1, total);
}C++
static void addColumns(TreeNode* node, int d, map<int, int>& total);
vector<int> verticalSum(TreeNode* root) {
map<int, int> total;
addColumns(root, 0, total);
vector<int> out;
for (auto& kv : total) out.push_back(kv.second);
return out;
}
static void addColumns(TreeNode* node, int d, map<int, int>& total) {
if (!node) return;
total[d] += node->val;
addColumns(node->left, d - 1, total);
addColumns(node->right, d + 1, total);
}JavaScript
var verticalSum = function(root) {
if (root === null) return [];
var total = {}, lo = 0, hi = 0;
var nodes = [root], ds = [0];
while (nodes.length > 0) {
var node = nodes.pop(), d = ds.pop();
total[d] = (total[d] || 0) + node.val;
if (d < lo) lo = d;
if (d > hi) hi = d;
if (node.left !== null) { nodes.push(node.left); ds.push(d - 1); }
if (node.right !== null) { nodes.push(node.right); ds.push(d + 1); }
}
var out = [];
for (var c = lo; c <= hi; c++) out.push(total[c]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)