Vertical Sum of a Binary Tree

Asked in:
Amazon

Problem Description

You are given the root of a binary tree A.
You have to find the vertical sum of the tree.
A vertical sum denotes an array of sum of the different verticals of a binary tree,
where the leftmost vertical sum is the first element of the array and rightmost vertical is the last.

Problem Constraints

1 <= Number of nodes in the binary tree <= 10⁵
1 <= A_i <= 10³

Input Format

The first argument is the root of a binary tree A.

Output Format

Return an array denoting the vertical sum of the binary tree.

Example Input

Input 1:

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

Input 2:

Example Output

Output 1:

[4, 2, 12, 3, 7]

Output 2:

[3, 2, 1]

Example Explanation

Explanation 1:

The element 4 is present in the leftmost vertical. 
The middle vertical consists of 3 elements 1, 5, 6.
The resultant array is [4, 2, 12, 3, 7].

Explanation 2:

The leftmost vertical is the element 3. The next verticals are 2 and 1.
Hence, the resultant array is [3, 2, 1].

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Vertical Sum of a Binary Tree on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

Amazon

Vertical Sum of a Binary Tree

Discussion