C++ Program to Implement a Binary Search Tree using Linked Lists

This C++ program, displays the traversal of a binary search tree in inorder,postorder and preorder mode using linked lists. A linked list is an ordered set of data elements, each containing a link to its successor.

Here is the source code of the C++ program which takes the value of root node and consecutively all other nodes as input and generates a binary search tree on the basis of the values of these nodes(all distinct). This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

```
/*
```

* C++ Program to Implement a Binary Search Tree using Linked Lists

```
 */
```
```
#include <iostream>
```
```
using namespace std;
```
```
#include <conio.h>
```
```
struct tree
```
```
{
```
```
    tree *l, *r;
```
```
    int data;
```

}*root = NULL, *p = NULL, *np = NULL, *q;

```
 
```
```
void create()
```
```
{
```
```
    int value,c = 0;   
```
```
    while (c < 7)
```
```
    {
```
```
        if (root == NULL)
```
```
        {
```
```
            root = new tree;
```

            cout<<"enter value of root node\n";

```
            cin>>root->data;
```
```
            root->r=NULL;
```
```
            root->l=NULL;
```
```
        }
```
```
        else
```
```
        {
```
```
            p = root;
```

            cout<<"enter value of node\n";

```
            cin>>value;
```
```
            while(true)
```
```
            {
```
```
                if (value < p->data)
```
```
                {
```
```
                    if (p->l == NULL)
```
```
                    {
```

                        p->l = new tree;

```
                        p = p->l;
```

                        p->data = value;

```
                        p->l = NULL;
```
```
                        p->r = NULL;
```

                        cout<<"value entered in left\n";

```
                        break;
```
```
                    }
```

                    else if (p->l != NULL)

```
                    {
```
```
                        p = p->l;
```
```
                    }
```
```
                }
```

                else if (value > p->data)

```
                {
```
```
                    if (p->r == NULL)
```
```
                    {
```

                        p->r = new tree;

```
                        p = p->r;
```

                        p->data = value;

```
                        p->l = NULL;
```
```
                        p->r = NULL;
```

                        cout<<"value entered in right\n";

```
		        break;
```
```
		    }
```

                    else if (p->r != NULL)

```
                    {
```
```
                        p = p->r;
```
```
                    }
```
```
                 }
```
```
             }
```
```
        }
```
```
        c++;
```
```
    }
```
```
}
```
```
void inorder(tree *p)
```
```
{
```
```
    if (p != NULL)
```
```
    {
```
```
        inorder(p->l);
```
```
        cout<<p->data<<endl;
```
```
        inorder(p->r);
```
```
    }
```
```
}
```
```
void preorder(tree *p)
```
```
{
```
```
    if (p != NULL)
```
```
    {
```
```
        cout<<p->data<<endl;
```
```
        preorder(p->l);
```
```
        preorder(p->r);
```
```
    }
```
```
}
```
```
void postorder(tree *p)
```
```
{
```
```
    if (p != NULL)
```
```
    {
```
```
        postorder(p->l);
```
```
        postorder(p->r);
```
```
        cout<<p->data<<endl;
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    create();
```

    cout<<"printing traversal in inorder\n";

```
    inorder(root);
```

    cout<<"printing traversal in preorder\n";

```
    preorder(root);
```

    cout<<"printing traversal in postorder\n";

```
    postorder(root);
```
```
    getch();
```
```
}
```

Output
enter value of root node
7
enter value of node
8
value entered in right
enter value of node
4
value entered in left
enter value of node
6
value entered in right
enter value of node
3
value entered in left
enter value of node
5
value entered in left
enter value of node
2
value entered in left
printing traversal in inorder
2
3
4
5
6
7
8
printing traversal in preorder
7
4
3
2
6
5
8
printing traversal in postorder
2
3
5
6
4
8
7

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Implement Sorted Circularly Doubly Linked List

» Next - C++ Program to Implement Queue using Linked List

Related Posts:

Check Programming Books
Check Data Structure Books
Practice Computer Science MCQs
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: