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
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.
Time complexity: O(n)