Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




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
                    

vertical sum in a given binary search tree

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





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in