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;xC 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