Posted on by Kalkicode
Code Binary Tree

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:

Vertical order sum of binary tree nodes

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

  1. Initialize an empty HashMap called record to store the vertical sums.
  2. Call the verticalSum function starting from the root node with an initial distance of 0.
  3. 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).
  4. After the traversal is complete, iterate through the record map, starting from distance 0, and print the vertical sums.
  5. Increment the distance by 1 in each iteration until all vertical sums are printed.

Code Solution

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 depth-first traversal, and the HashMap operations take constant time.

Comment

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