Vertical Sum of given Binary Tree
In this article, we will tackle the problem of calculating the vertical sum of a given binary tree. Vertical sum involves finding the sum of node values for each vertical column in the tree, where columns are defined based on horizontal distances from the root. We will explore how to implement this calculation in Java and print the sums for each vertical column.
Problem Statement
Given a binary tree, we want to calculate the vertical sum of the tree. Vertical sum means finding the sum of node values for each vertical column in the tree, where columns are determined by horizontal distances from the root. Columns to the left of the root have negative distances, the root column has a distance of 0, and columns to the right of the root have positive distances.
Example
Let's consider a binary tree as an example:
The vertical sum of this tree is [2, 8, 21, 22, 18]
. Each value in the sum represents the sum of node
values for a vertical column in the tree.
Idea to Solve the Problem
To calculate the vertical sum of a binary tree, we can use a recursive approach combined with a HashMap to store the sums for each vertical column. We start from the root with a distance of 0 and traverse the tree, updating the sums in the HashMap based on the horizontal distance from the root.
Pseudocode
Here is the pseudocode for solving the problem:
function verticalSum(node, distance, record):
if node is not null:
if distance not in record:
record[distance] = 0
record[distance] += node.data
verticalSum(node.left, distance  1, record)
verticalSum(node.right, distance + 1, record)
function printVerticalSum():
if root is null:
return
record = empty HashMap
verticalSum(root, 0, record)
distance = 0
while distance in record:
print record[distance]
increment distance by 1
Algorithm Explanation
 Initialize an empty
HashMap
calledrecord
to store the vertical sums.  Call the
verticalSum
function starting from the root node with an initial distance of 0.  In the
verticalSum
function: If the current node is not null, check if the current distance is already in
record
. If not, create a new entry with a sum of 0 for that distance.  Add the node's data to the sum associated with the current distance.
 Recursively call the function for the left child with a decremented distance (moving to the left).
 Recursively call the function for the right child with an incremented distance (moving to the right).
 If the current node is not null, check if the current distance is already in
 After the traversal is complete, iterate through the
record
map, starting from distance 0, and print the vertical sums.  Increment the distance by 1 in each iteration until all vertical sums are printed.
Code Solution

1) Vertical sum of binary tree in java
2) Vertical sum of binary tree in c++
3) Vertical sum of binary tree in golang
4) Vertical sum of binary tree in c#
5) Vertical sum of binary tree in vb.net
6) Vertical sum of binary tree in php
7) Vertical sum of binary tree in node js
8) Vertical sum of binary tree in python
9) Vertical sum of binary tree in ruby
10) Vertical sum of binary tree in scala
11) Vertical sum of binary tree in swift
12) Vertical sum of binary tree in kotlin
Time Complexity of the Code
The time complexity of this code is O(N), where N is the number of nodes in the binary tree. This is because we visit each node once during the depthfirst traversal, and the HashMap operations take constant time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment