C Code for Binary Search Tree Traversal

A Binary Search Tree is a Binary Tree datastructure (a tree in which each node has at most two children) which has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • The left and right subtree each must also be a binary search tree.
  • There must be no duplicate nodes.

Traversal of binary tree refers to the process of visiting each node one-by-one. For binary tree, we generally use the following 3 types of traversal:

  • Pre-Order

1. Visit the root.
2. Traverse the left subtree.
3. Traverse the right subtree.

  • In-Order

1. Traverse the left subtree.
2. Visit the root.
3. Traverse the right subtree.

  • Post-Order

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root.

As an example, let us consider the following binary tree :
binary search tree

For this tree, the Preorder traversal will be:
8, 3, 1, 6, 4, 7, 10, 14, 13

And the Inorder traversal will be:
1, 3, 4, 6, 7, 8, 10, 13, 14

And the Postorder traversal will be:
1, 4, 7, 6, 3, 13, 14, 10, 8

Here note that the Inorder traversal of a Binary Search tree results in an ascending order list.

Following is the C Code depicting the creation and traversal of a binary tree:

#include
#include

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node *root = NULL;

void insertNode(struct node *q, int data) {
    if(q == NULL) {
        // create the 1st node (root)
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->left = NULL;
        p->right = NULL;
        p->data = data;
        root = p;
        return;
    }
    else if(data < q->data && q->left != NULL) {
        q = q->left;
        insertNode(q,data);
    }
    else if(data > q->data && q->right != NULL) {
        q = q->right;
        insertNode(q,data);
    }
    else if(q->left == NULL && data < q->data) {
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->data = data;
        p->right = NULL;
        p->left = NULL;
        q->left = p;
        return;
    }
    else if(q->right == NULL && data > q->data) {
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->data = data;
        p->right = NULL;
        p->left = NULL;
        q->right = p;
        return;
    }
}

void inOrderTrav(struct node *q) {
    if(q != NULL) {
        inOrderTrav(q->left);
        printf("%d\n",q->data);
        inOrderTrav(q->right);
    }
}

void preOrderTrav(struct node *q) {
    if(q != NULL) {
        printf("%d\n",q->data);
        preOrderTrav(q->left);
        preOrderTrav(q->right);
    }
}

void postOrderTrav(struct node *q) {
    if(q != NULL) {
        postOrderTrav(q->left);
        postOrderTrav(q->right);
        printf("%d\n",q->data);
    }
}

void main() {
    int n;
    int num_nodes = 7;
    for(int x=0;x<num_nodes;x++) {
        printf("Enter new node of BST ");
        scanf("%d",&n);
        insertNode(root,n);
    }

    printf("\nInorder Traversal is:\n");
    inOrderTrav(root);

    printf("\nPreorder Traversal is:\n");
    preOrderTrav(root);

    printf("\nPostorder Traversal is:\n");
    postOrderTrav(root);
}

The output of this program, after compilation will be something like:
C Code for Binary Search Tree


Related Posts

Share

Filed Under: CCodesData Structures

Tags:

About the Author: Software Engineer - Advanced Search & Recommendation at Rovi

RSSComments (2)

Leave a Reply | Trackback URL

  1. kundan says:

    one of the best work!!!!

  2. mandar says:

    it is really very helpful but it will be great if u provide other codes also like counting sort , etc .

Leave a Reply

*

AWSOM Powered