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.