Explore
Placement Prep

Edit

Edit

# Find the vertical sum in a given binary search tree | FACE Prep

Published on 10 Mar 2020

Program to find the vertical sum in a given binary search tree is discussed here. A binary search tree is given as input and the sum of all nodes that are in the same vertical line is produced as output.

For example, consider the given binary search tree.

             10
/   \
8      12
/ \     / \
4   9 11  14

Vertical line - 1 : 4
Vertical line - 2 : 8
Vertical line - 3 : 10 + 9 + 11 = 30
Vertical line - 4 : 12
Vertical line - 5 : 14



## Algorithm to find the vertical sum in a given binary search tree

1. Input the given binary search tree.
2. Create a doubly linked list and initializenode = 0 with its next and prev pointers referenced to NULL.
3. Call the functionvsum(tree)

vsum(tree)

1. Create node and initialize them.
call the functionvsum_list(tree, sums)
2. while(sums->prev != NULL)
3. sums = sums->prev;
4. while(sums != NULL)
5. print sums->element
6. sums = sums->next // move to next node

vsum_list(tree, sums)

1. if(tree == NULL)
2. return
3. node -> element = node -> element + tree->element;
4. if(tree->left) andif(node->prev == NULL) // left sub-tree
5. node -> prev = create_node(0, node, NULL) // Assign node = 0, next pointer = node and prev pointer = NULL
6. Call the functionvsum_list(tree -> left, node -> prev)
7. if(tree -> right) andif(node -> next == NULL)
node->next = create_node(0, NULL, node) // Assign node = 0, next pointer = NULL and prev pointer = node
8. Call the functionvsum_list(tree -> right, node -> next)


Program to find the vertical sum in a given binary search tree is given below.

C
C++

Output
Input - Enter the number of elements of the tree : 6 Input the tree elements : 10 8 12 4 9 14 Output - Vertical Sum : 4 8 19 12 14

Time complexity: O(n)

Recommended Programs