Binary Search Tree inorder traversal – C Program

BST – Binary Search Tree inorder traversal program in C. This program will first prepare a binary search tree by create a tree node and insert function and then perform inorder traversal using recursion technique.

Time complexity = O(n).

Note that BST property is that Left subtree Value will be less that Root value and Root value will be less than the right subtree values.

BST Property :

Left Value < Root Value < Right Value

Inorder Traversal Rule:

Left, Root, Right

—–Snips of the inorder traversal function in C using recursion —-

/*
 In order traversal function.
 */
void inorder(node *root) {
	
   if (root != NULL) {
	   //visit all left childs
      inorder(root->leftChild);
	  //visit the root
      printf("%d ", root->data);
	  //visti all right childs
      inorder(root->rightChild);
   }
}

NOTE: In order traversal of BST (Binary Search Tree) produces sorted elements in ascending order.

BST program in C – Inorder traversal

/*Create a node for tree*/
typedef struct BST {
   int data;
   struct BST *leftChild, *rightChild;
} node;

/*
 In order traversal function.
 */
void inorder(node *root) {
	
   if (root != NULL) {
	   //visit all left childs
      inorder(root->leftChild);
	  //visit the root
      printf("%d ", root->data);
	  //visti all right childs
      inorder(root->rightChild);
   }
}


/*Create a new node*/
node *newNode(int data) {
   node *temp;
   //Create a memory chunk of size node structure
   temp = (node *) malloc(sizeof(node));
   if(temp == NULL)
    {
        fprintf (stderr, "Memory failure \n");
        exit(1);
    }

   //fill data in the node

   temp->data = data;
  //Since it is a new node, left and right child
  
   temp->leftChild = NULL;
   temp->rightChild = NULL;
   //Return the pointer of the node
   return temp;
}

/*Insert the node into the tree*/
node* insert(node *root, int data)
{
 
    if(root == NULL)
    {
		//Create first root node
        root = newNode(data);
    }
    else
    {
		if (data < root->data){

			root->leftChild  = insert(root->leftChild, data);
		}else{
			 root->rightChild = insert(root->rightChild, data);
		} 
    }

    return root;
}
int main(){

	struct node *bst = NULL;

	//Prepare a BST 
    bst = insert(bst, 70);
    insert(bst, 10);
	insert(bst, 90);
	insert(bst, 40);
	insert(bst, 30);
	insert(bst, 60);	
	  
    //Do the in order traversal of BST
	//In order traversal will print sorted
	//data in ascending order
    inorder(bst);

	return 0;
}

Output:
10 30 40 60 70 90