Vertical Sum of Binary Tree

Medium
1967.

Vertical Sum of Binary Tree

Vertical Sum of Binary Tree is a medium coding problem on hash table, depth-first search and trees, asked in Amazon interviews.

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^4
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var verticalSum = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 1 <= Node.val <= 10^5

Hints for Vertical Sum of Binary Tree

  1. Hint 1

    Give each node its horizontal distance from the root: root 0, left child − 1, right child + 1.

  2. Hint 2

    Any traversal works — accumulate each node's value into the total for its distance.

  3. 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

  1. Traverse the tree (DFS or BFS) carrying the line number: left child d - 1, right child d + 1.
  2. Add the node's value to total[d] and update the smallest and largest d seen.
  3. 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)