Creating and traversing a binary search tree

The need:

     This program is written to show creation and various types of printing of a binary search tree. This program takes values and put them in a binary search tree and then prints the resulting tree in preorder, inorder and post order.
 The BST(Binary Search tree): a binary search tree is a binary tree in which value of each node is greater or equal than that of its left child and less than that of its right child. Hence all nodes in the left sub-tree of a node are less than or equal to the value of that node and all nodes in the right sub-tree of a node are greater than the value of that node if it is a binary search tree. We'll use this property while inserting a node in the BST in insert() function.

The code:

----------------------------------------------------------

#define MAX 10
#define DEBUG if(!(root->left))    printf("inserted %d to the left of %d\n",x,root->data);
#include<stdio.h>
#include<stdlib.h>
struct tree_node
{
    int data;
    struct tree_node *left,*right,*parent;
};
typedef struct tree_node node;
node * new_node(int x);
node * insert_node(node *root, int x);
void print_preorder(node *root);
void print_inorder(node *root);
void print_postorder(node *root);

int main()
{
    node *root=NULL;
    int i;
    int arr[]={5,6,1,9,0,4,2,3,8,7};
    for(i=0;i<MAX;i++)
    root = insert_node(root, arr[i]);
    printf("\ntree pre order is\n");
    print_preorder(root);
    printf("\n\ntree in order is\n");
    print_inorder(root);
    printf("\n\ntree post order is\n");
    print_postorder(root);
    return 0;
}

node * insert_node(node *root, int x)
{
    if(!root)
    {
        root = new_node(x);
        return root;
    }
    if(root->data > x)
    {
//        DEBUG
        root->left = insert_node(root->left,x);
    }
    else
    {
//        DEBUG
        root->right = insert_node(root->right,x);
    }
    return root;
}

void print_preorder(node *root)
{
    if(!root)
    return;
    printf("%d ",root->data);
    print_preorder(root->left);
    print_preorder(root->right);
    return;
}

void print_inorder(node *root)
{
    if(!root)
    return;
    print_inorder(root->left);
    printf("%d ",root->data);
    print_inorder(root->right);
    return;
}

void print_postorder(node *root)
{
    if(!root)
    return;
    print_postorder(root->left);
    print_postorder(root->right);
    printf("%d ",root->data);
    return;
}

node * new_node(int x)
{
    node *furnished;
    furnished = (node*)malloc(sizeof(node));
    furnished->data=x;
    furnished->left=NULL;
    furnished->right=NULL;
    furnished->parent=NULL;
    return furnished;
}

----------------------------------------------------------

Approach:

    This program is just to show the printing of a tree in pre-order, inorder and post order. For that first we have to make the tree. Here we dont have tree with 3 nodes necessarily. So we need to make a function to construct the tree. Here insert() function does the job. create_node() function creates a node with given data/value ans returns it address. we create first node, make it root. After that we create 2 more nodes and make them left and right children of root. Then there are 3 functions in_print(), pre_print() and post_print() which print the expression in infix, prefix and postfix form respectively.

Remarks:

1. We noticed that here in each function I have used recursion like I have already said in previous posts that recursion makes our life easier in trees.
2. Uncomment DEBUG to see where the nodes are being inserted.
3. Here I am taking node data from an array we can take data from user also.

Inorder, Preorder and Post-Order traversal of tree

The need:

     This program is written to show the program implementation of the concept explained in the previous post. This program is the implementation of 2 + 3 example given there.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct tree
{
    char num;
    struct tree *left, *right, *parent;
};
typedef struct tree node;

void in_print(node *p);
void pre_print(node *p);
void post_print(node *p);
node * create_node(char c);
int main()
{
    int i;
    node *root=NULL;
    root = create_node('+');
    root->left = create_node('a');
    root->right = create_node('b');
    printf("Pre order print\t\t");
    pre_print(root);
    printf("\nIn order print\t\t");
    in_print(root);
    printf("\nPost order print\t");
    post_print(root);
    putchar('\n');
    return 0;
}

node * create_node(char c)
{
    node *new_node;
    new_node = (node *)malloc(sizeof(node));
    new_node->num = c;
    new_node->parent = NULL;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void pre_print(node *p)
{
    if(p==NULL)
    return;
    else
    printf("%c ",p->num);
    pre_print(p->left);
    pre_print(p->right);
}

void in_print(node *p)
{
    if(p==NULL)
    return;
    else
    in_print(p->left);
    printf("%c ",p->num);
    in_print(p->right);
}

void post_print(node *p)
{
    if(p==NULL)
    return;
    else
    post_print(p->left);
    post_print(p->right);
    printf("%c ",p->num);
}

----------------------------------------------------------

Approach:
    This program is just to show the printing of a tree in pre-order, inorder and post order. For that first we have to make the tree. Here I have not created a bigger tree. Here we have the simplest tree with 3 nodes only. So we need not make a function to construct the tree. Here simply I have created 3 nodes and put them to make a small tree. create_node() function creates a node with given data/value ans returns it address. we create first node, make it root. After that we create 2 more nodes and make them left and right children of root. Then there are 3 functions in_print(), pre_print() and post_print() which print the expression in infix, prefix and postfix form respectively.
Remarks:

1. Here this program is shown to print the simplest expression in prefix, infix and post-fix form but this program can be used to print any binary tree in pre-order, inorder and post order.

2. This program is the base of all the tree programs related to trees.

Inorder, Preorder and Post-Order traversal : An overview

The Idea:
Lets first have a look at some mathematical side. The Infix, Prefix and Post-fix notations are exactly analogous to the In-order, Preorder and Post-order traversal of trees.
Have a look at the expresstion:
a + b
     This is a familiar expression to all of us. Here + is an operator with a and b as operands. This is one way to write sum of a and b. This way is called in-fix notation. In this way we write operator in between the operands. This is the only used method for writing expressions for human understanding. Thats why everybody is familiar to this method. But this is not the only way to be used for every purpose. there are 2 more ways.
     Prefix notation: In this way of writing expressions the operator comes first which is followed by the operators. The same expression can be written in Prefix notation as:
+ a b
     Postfix notation: In this way of writing expressions the operator comes last after both the operands have been written. The same expression can be written in Prefix notation as: 
a b +

Analogy comes from here. Have a look at the above image.
Its a tree with + at parent node and 2 and 3 as child nodes. Now we have
Infix: 2 + 3
Prefix: + 2 3
postfix: 2 3 +
    We see that it is the position of operator which changes and decides which fix notation is this. The relative positions of operands are always same.
    This is about expressions writing. Now lets move to traversal of trees in data-structures topic. In the same manner as in the case of expressions in trees also left child will always be accessed before the right. It is the root which decides which type of traversal it is.
     InOrder Traversal: In this way of traversing tree the root is accessed first after that the children are accessed.
     PreOrder Traversal: In this way of traversing tree one child is accessed first and then the root is accessed after that the other child is accessed.
     PostOrder Traversal: In this way of traversing tree the root is accessed after both of the children are accessed.
   here this concept is explained with the basic tree consisting of only 3 nodes but this holds true for any tree(binary tree). Recursion will play very important role in tree traversal. We can store a mathematical expression in tree and then that can be printed in any order using inorder, preorder and postorder traversal giving infix, prefix and post-fix form of that expression respectively. Obviously this is not the only use of trees.

Concept of trees in C:

The concept of trees is same to real world tree. In real word every tree has roots, and can have many branches. Each branch can have sub-branches. If you look at branches and sub-branches as a whole, the combination looks like a tree (lets call it a sub-tree). Same is the case of a tree in programming jargon. There is only one difference in plotting the trees. A real world tree has roots on the downside while in C programming, a tree is upside down which has roots on the top and sub-trees below that. Tree is a variation of linked lists.

Here in programming the most commonly used tree is a binary tree. Now lets come to data-structural jargon. A binary tree is a tree in a tree (data structure) in which each node (say current node) has addresses of 2 next possible nodes. The current node is called parent node and these next 2 nodes are called children of that node. We'll call them left child and right child. From the current node, if you want to come down, you have 2 options (either you can come on left child or the right child).

You people have seen that we can traverse a singly linked list in one direction and doubly linked list in two directions in the similar way in a tree you can reach max three nodes from a current node. So in a binary tree each node has only 2 address pointers, you can traverse only in the down direction. If you want to traverse the tree in both the directions (downward as well as upward), each node must be having address of its parent node also.

Here the node structure is a bit different. You can think of a binary tree as a continuation of linked lists from singly to doubly to binary tree. Let me explain further. In node of a singly connected linked list we have one single pointer pointing to next node and in node of a doubly connected linked list we have 2 pointers which can point to other 2 nodes (next and previous nodes). Similarly in a node of a binary tree we have 3 pointers which can point to 3 other nodes one to parent, one to left child, one to right child so that we can traverse easily in both the directions.

program to print a linked list in reverse order

The need: 

     This program is a program to prints a linked list in reverse order without actually reversing it (For reversing a given linked list have a look on program78 of this blog). This program is written to show how recursion becomes more useful. First it asks user to enter numbers to be entered into linked list then creates a linked list, prints it in same as given and reversed order.

The code: 

---------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
typedef struct linked_list
{
    int item;
    struct linked_list *next;
}node;

node *create_list();
void print_list(node *);
void print_list_in_reverse(node *);

int main()
{
    node *head=NULL;
    printf("This program creates a linked list and then prints it first in given order and then in reverse\n");
    printf("create a list by entering elements press -999 to end\n");
    head=create_list();
    printf("\nThe list is\n");
    print_list(head);
    printf("\nThe list in reverse order is");
    print_list_in_reverse(head);
    printf("\n");
    return 0;
}

node *create_list()
{
    int x;
    node *temp=NULL;
    scanf("%d",&x);
    if(x!=-999)
    {
        temp=(node*)malloc(sizeof(node));
        temp->item=x;
        temp->next=NULL;
        temp->next=create_list();
    }
    return temp;
}
void print_list(node *p)
{
    if(p)
    {
        printf("%d ",p->item);
        print_list(p->next);
    }
    else
    printf("\n");
}

void print_list_in_reverse(node *p)
{
    if(p)
    {
        print_list_in_reverse(p->next);
        printf("%d ",p->item);
    }
    else
    printf("\n");
}

---------------------------------------------------------

The need:

   The approach is nothing but basics of recursion.
If we say the recursion in create_list function in normal English, we'll say "It will take a number form user if it is not -999, a new node is created, data is filled in it and address of this node is returned else NULL is returned." because temp is initialised to NULL each time in the starting of function.

If we say the recursion in print_list function in normal English, we'll say "It will print the data of a node and then go for doing the same to the next node after that if present".

If we say the recursion in print_list_in_reverse function in normal English, we'll say "It will print the data of a node when all the node after that are printed or if there is no node after that node".

 

Remarks:

1. We can print linked list as it is (in the given order) without using extra storage or extra thinking. We can just use loops but if we are asked to write a program to print the linked list without actually reversing it, we can not do it by just using loops. What we can do is next point.

2. For that we have to create a stack and push addresses of all the elements of linked list on it starting from head to end. Then pop addresses one by one and print the corresponding data. This requires extra storage and extra thinking.

3. So in this program recursion is the way to do the same without extra thinking and without explicitly using extra memory and functions.

4. I wrote explicitly with stress because recursion actually uses its own stack (System stack). Now I am not going into these details.