# 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

Binary Search Tree inorder traversal – C Program

Scroll to top