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.

1. `/*`
2. ` * C Program to find the Total Columns/Vertical Lines of a given `
3. ` * Binary Search Tree`
4. ` `
5. `    40`
6. `   /  \`
7. `  20   60`
8. ` /  \    \`
9. `10  30   80`
10. `          \`
11. `          90`
12. `(40,60,80,20,30,90,10)    `
13. `(Binary search tree)         `
14. ` */`
15. `#include <stdio.h>`
16. `#include <stdlib.h>`
17. ` `
18. `struct btnode {`
19. `    int value;`
20. `    int col;`
21. `    struct btnode *l;`
22. `    struct btnode *r;`
23. `};`
24. ` `
25. `typedef struct btnode bt;`
26. ` `
27. `bt *root,*temp;`
28. `bt *new;`
29. `int min = 0, max = 0;`
30. ` `
31. `bt * create_node();`
32. `void display(bt *);`
33. `void insert(bt *, bt *);`
34. `void columns(bt *);`
35. ` `
36. `void main()`
37. `{`
38. `    int num;`
39. ` `
40. `    while (1)`
41. `    {`
42. `        printf("enter the number:");`
43. `        scanf("%d", &num);`
44. `        if (num == 0)`
45. `        {`
46. `            break;`
47. `        }`
48. `        create_node();`
49. `        new->value = num;`
50. `        if (root == NULL)`
51. `        {`
52. `            root = new;`
53. `            root->col = 0;`
54. `        }`
55. `        else`
56. `        {`
57. `            insert(new,root);`
58. `        }    `
59. `    }`
60. `    display(root);`
61. `    columns(root);`
62. `    printf("\n total number of columns : %d",-min + max + 1);`
63. `}`
64. ` `
65. `/* creates new node */`
66. `bt * create_node()`
67. `{`
68. `    new=(bt *)malloc(sizeof(bt));`
69. `    new->l = NULL;`
70. `    new->r = NULL;`
71. `}`
72. ` `
73. `/* inserts the node into tree */`
74. `void insert(bt * new , bt * list)`
75. `{`
76. `    if (new->value>list->value)`
77. `    {`
78. `        if (list->r == NULL)`
79. `        {`
80. `            list->r = new;`
81. `            new->col = list->col + 1;`
82. `        }`
83. `        else`
84. `        {`
85. `            insert (new,list->r);`
86. `        }        `
87. `    }`
88. `    if (new->value < list->value)`
89. `    {`
90. `        if (list->l == NULL)`
91. `        {`
92. `            list->l = new;`
93. `            new->col = list->col - 1;`
94. `        }`
95. `        else`
96. `        {`
97. `            insert (new,list->l);`
98. `        }`
99. `    }`
100. `}`
101. ` `
102. `/* displays the elements in the tree using inorder */`
103. `void display(bt * list)`
104. `{`
105. `    if (list == NULL)`
106. `    {`
107. `        return;`
108. `    }`
109. `    display(list->l);`
110. `    printf("->%d", list->value);`
111. `    display(list->r);    `
112. `}`
113. ` `
114. `/* counts the number of columns in tree */`
115. `void columns(bt * list)`
116. `{`
117. `    if (list == NULL)`
118. `    {`
119. `        return;`
120. `    }`
121. `    if (list->col < min)`
122. `    {`
123. `        min = list->col;`
124. `    }`
125. `    if (list->col > max)`
126. `    {`
127. `        max = list->col;`
128. `    }`
129. `    columns(list->l);`
130. `    columns(list->r);`
131. `}`

```     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.