C Program to Find the Total Columns/Vertical Lines of a Binary Search Tree

This C Program find the total columns/vertical lines of a given binary search tree.

Here is source code of the C Program to find the total columns/vertical lines of a given binary search tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```

 * C Program to find the Total Columns/Vertical Lines of a given

```
 * Binary Search Tree
```
```
 
```
```
    40
```
```
   /  \
```
```
  20   60
```
```
 /  \    \
```
```
10  30   80
```
```
          \
```
```
          90
```
```
(40,60,80,20,30,90,10)    
```
```
(Binary search tree)         
```
```
 */
```
```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct btnode {
```
```
    int value;
```
```
    int col;
```
```
    struct btnode *l;
```
```
    struct btnode *r;
```
```
};
```
```
 
```
```
typedef struct btnode bt;
```
```
 
```
```
bt *root,*temp;
```
```
bt *new;
```
```
int min = 0, max = 0;
```
```
 
```
```
bt * create_node();
```
```
void display(bt *);
```
```
void insert(bt *, bt *);
```
```
void columns(bt *);
```
```
 
```
```
void main()
```
```
{
```
```
    int num;
```
```
 
```
```
    while (1)
```
```
    {
```
```
        printf("enter the number:");
```
```
        scanf("%d", &num);
```
```
        if (num == 0)
```
```
        {
```
```
            break;
```
```
        }
```
```
        create_node();
```
```
        new->value = num;
```
```
        if (root == NULL)
```
```
        {
```
```
            root = new;
```
```
            root->col = 0;
```
```
        }
```
```
        else
```
```
        {
```
```
            insert(new,root);
```
```
        }    
```
```
    }
```
```
    display(root);
```
```
    columns(root);
```

    printf("\n total number of columns : %d",-min + max + 1);

```
}
```
```
 
```
```
/* creates new node */
```
```
bt * create_node()
```
```
{
```
```
    new=(bt *)malloc(sizeof(bt));
```
```
    new->l = NULL;
```
```
    new->r = NULL;
```
```
}
```
```
 
```
```
/* inserts the node into tree */
```
```
void insert(bt * new , bt * list)
```
```
{
```
```
    if (new->value>list->value)
```
```
    {
```
```
        if (list->r == NULL)
```
```
        {
```
```
            list->r = new;
```
```
            new->col = list->col + 1;
```
```
        }
```
```
        else
```
```
        {
```
```
            insert (new,list->r);
```
```
        }        
```
```
    }
```
```
    if (new->value < list->value)
```
```
    {
```
```
        if (list->l == NULL)
```
```
        {
```
```
            list->l = new;
```
```
            new->col = list->col - 1;
```
```
        }
```
```
        else
```
```
        {
```
```
            insert (new,list->l);
```
```
        }
```
```
    }
```
```
}
```
```
 
```

/* displays the elements in the tree using inorder */

```
void display(bt * list)
```
```
{
```
```
    if (list == NULL)
```
```
    {
```
```
        return;
```
```
    }
```
```
    display(list->l);
```
```
    printf("->%d", list->value);
```
```
    display(list->r);    
```
```
}
```
```
 
```

/* counts the number of columns in tree */

```
void columns(bt * list)
```
```
{
```
```
    if (list == NULL)
```
```
    {
```
```
        return;
```
```
    }
```
```
    if (list->col < min)
```
```
    {
```
```
        min = list->col;
```
```
    }
```
```
    if (list->col > max)
```
```
    {
```
```
        max = list->col;
```
```
    }
```
```
    columns(list->l);
```
```
    columns(list->r);
```
```
}
```

     40
    /  \
   20   60
  /  \    \                                         
10   30   80
            \
             90
$ cc tree41a.c
$ a.out
enter the number:40
enter the number:20
enter the number:60
enter the number:80
enter the number:90
enter the number:10
enter the number:30
enter the number:0
->10->20->30->40->60->80->90
total number of columns : 6

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

« Prev - C Program to Convert Binary Tree to Binary Search Tree

» Next - C Program to Find the Sum of all Nodes in a Tree

Related Posts:

Recommended Articles: