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.

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 initialize node = 0 with its next and prev pointers referenced to NULL.
3. Call the function vsum(tree)

vsum(tree)

1. Create node and initialize them.
call the function vsum_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) and  if(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 function vsum_list(tree -> left, node -> prev)

7. if(tree -> right) and if(node -> next == NULL)
node->next = create_node(0, NULL, node)   // Assign node = 0, next pointer = NULL and prev pointer = node
8. Call the function vsum_list(tree -> right, node -> next)
 

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

// C program to find the vertical sum in a given binary search tree

#include <stdio.h>
#include <malloc.h>
#include <string.h>

struct Tree {
int element;
struct Tree *left;
struct Tree *right;
};

typedef struct Tree* TREE;

TREE create_tnode(int element, TREE left, TREE right) {
TREE tree = (TREE) malloc(sizeof(struct Tree));
tree->element = element;
tree->left = left;
tree->right = right;
return tree;
}

TREE insert_tree(TREE tree, int element) {
if(tree == NULL){
return create_tnode(element, NULL, NULL);
} else if(element > tree->element){
tree->right = insert_tree(tree->right, element);
} else if(element < tree->element) {
tree->left = insert_tree(tree->left, element);
} else {
// Duplicate, Do nothing
}
return tree;
}

TREE destroy_tree(TREE tree) {
if(tree != NULL){
destroy_tree(tree->left);
destroy_tree(tree->right);
free(tree);
}
return NULL;
}

struct List {
int element;
struct List *next;
struct List *prev;
};

typedef struct List* LIST;

LIST create_node(int element, LIST next, LIST prev) {
LIST list = (LIST) malloc(sizeof(struct List));
list->element = element;
list->next = next;
list->prev = prev;
return list;
}

void vsum_list(TREE tree, LIST node) {
if(tree == NULL){
return;
}
node->element += tree->element;
if(tree->left){
if(node->prev == NULL){
node->prev = create_node(0, node, NULL);
}
vsum_list(tree->left, node->prev);
}
if(tree->right){
if(node->next == NULL){
node->next = create_node(0, NULL, node);
}
vsum_list(tree->right, node->next);
}
}

// TODO: Implement the following function
void vsum(TREE tree)
{
LIST c = NULL;
LIST sums = create_node(0, NULL, NULL);
vsum_list(tree, sums);
while(sums->prev != NULL){
sums = sums->prev;
}
while(sums != NULL){
printf(“%d “, sums->element);
sums = sums->next;
}
printf(“\n”);
}

void print_infix(TREE tree){
if(tree == NULL){
return;
}
print_infix(tree->left);
printf(“%d “, tree->element);
print_infix(tree->right);
}

int main()
{
int n;
int x, i;
char command[10];
TREE tree = NULL;
printf(“\nEnter the number of elements of the tree : “);
scanf(“%d”, &n);
printf(“\nInput the tree elements : “);
for (i = 0; i < n; i++)
{
scanf(“%d”, &x);
tree = insert_tree(tree, x);
}
printf(“\nVertical sum : “);
vsum(tree);
tree = destroy_tree(tree);
return 0;

// C++ program to find the vertical sum in a given binary search tree

#include <bits/stdc++.h>
using namespace std;

struct Tree
{
int element;
struct Tree *left;
struct Tree *right;
};

typedef struct Tree* TREE;

TREE create_tnode(int element, TREE left, TREE right) {
TREE tree = (TREE) malloc(sizeof(struct Tree));
tree->element = element;
tree->left = left;
tree->right = right;
return tree;
}

TREE insert_tree(TREE tree, int element) {
if(tree == NULL){
return create_tnode(element, NULL, NULL);
} else if(element > tree->element){
tree->right = insert_tree(tree->right, element);
} else if(element < tree->element) {
tree->left = insert_tree(tree->left, element);
} else {
// Duplicate, Do nothing
}
return tree;
}

TREE destroy_tree(TREE tree) {
if(tree != NULL){
destroy_tree(tree->left);
destroy_tree(tree->right);
free(tree);
}
return NULL;
}

struct List {
int element;
struct List *next;
struct List *prev;
};

typedef struct List* LIST;

LIST create_node(int element, LIST next, LIST prev) {
LIST list = (LIST) malloc(sizeof(struct List));
list->element = element;
list->next = next;
list->prev = prev;
return list;
}

void vsum_list(TREE tree, LIST node) {
if(tree == NULL){
return;
}
node->element += tree->element;
if(tree->left){
if(node->prev == NULL){
node->prev = create_node(0, node, NULL);
}
vsum_list(tree->left, node->prev);
}
if(tree->right){
if(node->next == NULL){
node->next = create_node(0, NULL, node);
}
vsum_list(tree->right, node->next);
}
}

// TODO: Implement the following function
void vsum(TREE tree)
{
LIST c = NULL;
LIST sums = create_node(0, NULL, NULL);
vsum_list(tree, sums);
while(sums->prev != NULL){
sums = sums->prev;
}
while(sums != NULL){
cout << sums->element << ” “;
sums = sums->next;
}
cout << endl;
}

void print_infix(TREE tree){
if(tree == NULL){
return;
}
print_infix(tree->left);
cout << tree->element << ” “;
print_infix(tree->right);
}

int main()
{
int n;
int x, i;
char command[10];
TREE tree = NULL;
cout << “\nEnter the number of elements of the tree : “;
cin >> n;
cout << “\nInput the tree elements : “;
for (i = 0; i < n; i++)
{
cin >> x;
tree = insert_tree(tree, x);
}
cout << “\nVertical sum : “;
vsum(tree);
tree = destroy_tree(tree);
return 0;
}