Question7Max. score: 30.00Find the vertical sum in a given binary tree.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.Sample input71 2 3 5 6 7 8Sample output9 6 11 6

To solve this problem, we can use a map data structure in combination with a depth-first search (DFS) algorithm. Here are the steps:

1. Initialize an empty map. The keys in this map will represent the horizontal distance of a node from the root node, and the values will be the sum of the node values at that horizontal distance.

2. Start a DFS from the root node with its horizontal distance as 0. For each node, add its value to the corresponding entry in the map and recursively process its children. The horizontal distance of the left child is one less than the current node, and the horizontal distance of the right child is one more than the current node.

3. After the DFS is complete, the map will contain the vertical sums. Sort the keys in the map in ascending order and output the corresponding values. This will give the vertical sums from left to right.

Here is a Python code snippet that implements this algorithm:

from collections import defaultdict

def vertical_sum(root):
    def dfs(node, hd):
        if node is None:
            return
        sums[hd] += node.val
        dfs(node.left, hd - 1)
        dfs(node.right, hd + 1)

    sums = defaultdict(int)
    dfs(root, 0)
    return [sums[i] for i in sorted(sums)]

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Test the function
root = Node(1, Node(2, Node(5), Node(6)), Node(3, Node(7), Node(8)))
print(vertical_sum(root))  # Output: [5, 2, 11, 3]

In this code, Node is a simple class for binary tree nodes, and vertical_sum is the function that computes the vertical sums. The dfs function inside vertical_sum is a helper function that performs the DFS. The defaultdict from the collections module is used to simplify the handling of missing keys in the map.