Find the vertical sum in a given binary search tree | faceprep

Find the vertical sum in a given binary search tree | faceprep

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.




Find the vertical sum in a given binary search tree



For example, consider the given binary search tree.


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



Find the 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.n2. Create a doubly linked list and initializenode = 0 with its next and prev pointers referenced to NULL.n3. Call the functionvsum(tree)nnvsum(tree)nn1. Create node and initialize them.ncall the functionvsum_list(tree, sums)n2. while(sums->prev != NULL)n3. sums = sums->prev;n4. while(sums != NULL)n5. print sums->elementn6. sums = sums->next // move to next nodennvsum_list(tree, sums)nn1. if(tree == NULL)n2. returnn3. node -> element = node -> element + tree->element;n4. if(tree->left) andif(node->prev == NULL) // left sub-treen5. node -> prev = create_node(0, node, NULL) // Assign node = 0, next pointer = node and prev pointer = NULLn6. Call the functionvsum_list(tree -> left, node -> prev)n7. if(tree -> right) andif(node -> next == NULL)nnode->next = create_node(0, NULL, node) // Assign node = 0, next pointer = NULL and prev pointer = noden8. Call the functionvsum_list(tree -> right, node -> next)n



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




@@coding::1@@


Time complexity: O(n)



Recommended Programs






Find the vertical sum in a given binary search tree