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 <stdio.h>
    #include <stdlib.h>
    
    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 (1)

    Leave a Reply | Trackback URL

    1. kundan says:

      one of the best work!!!!

    Leave a Reply

    *

    AWSOM Powered