How to do it... – inorder traversal of the tree

Because it's a recursive form, the function will be called recursively. The function is as follows:

inorder(node)

Here, inorder is the function that will be recursively called and node is the node of the binary tree that's being passed to it. Initially, the node will be the root of the binary tree, whose inorder traversal is required. Follow these steps:

1. If node is NULL, go to step 2; otherwise, return to the caller function.

2. Call the same function (the inorder function) with the node's left child set as an argument:

call inorder(node->leftchild)

3. Display the content in the node:

display node->info

4. Call the same function itself (the inorder function) with the node's right child set as an argument:

   call inorder(node->rightchild)

The program for creating a binary search tree and traversing it in inorder is as follows:

//binarysearchtree.c

#include <stdio.h>

#include <stdlib.h>

#define max 20
struct tree {
  int data;
  struct tree * right;
  struct tree * left;
};
void build(int Arr[], int Len);
struct tree * makeroot(int val);
void rightchild(struct tree * rootNode, int val);
void leftchild(struct tree * rootNode, int val);
void travino(struct tree * node);
int main() {
  int arr[max], i, len;
  printf("How many elements are there for making the binary search tree? ");
  scanf("%d", & len);
  printf("Enter %d elements in array \n", len);
  for (i = 0; i < len; i++)
    scanf("%d", & arr[i]);
  build(arr, len);
  return 0;
}

void build(int Arr[], int Len) {
  struct tree * temp, * rootNode;
  int j;
  rootNode = makeroot(Arr[0]);
  for (j = 1; j < Len; j++) {
    temp = rootNode;
    while (1) {
      if (Arr[j] < temp - > data) {
        if (temp - > left != NULL) {
          temp = temp - > left;
          continue;
        }
        leftchild(temp, Arr[j]);
      }
      if (Arr[j] > temp - > data) {
        if (temp - > right != NULL) {
          temp = temp - > right;
          continue;
        }
        rightchild(temp, Arr[j]);
      }
      break;
    }
  }
  printf("Binary Search Tree is created\n");
  printf("The inorder traversal of the tree is as follows:\n");
  travino(rootNode);
}

struct tree * makeroot(int val) {
  struct tree * rootNode;
  rootNode = (struct tree * ) malloc(sizeof(struct tree));
  rootNode - > data = val;
  rootNode - > right = NULL;
  rootNode - > left = NULL;
  return rootNode;
}

void leftchild(struct tree * rootNode, int val) {
  struct tree * newNode;
  newNode = (struct tree * ) malloc(sizeof(struct tree));
  newNode - > data = val;
  newNode - > left = NULL;
  newNode - > right = NULL;
  rootNode - > left = newNode;
}

void rightchild(struct tree * rootNode, int val) {
  struct tree * newNode;
  newNode = (struct tree * ) malloc(sizeof(struct tree));
  newNode - > data = val;
  newNode - > left = NULL;
  newNode - > right = NULL;
  rootNode - > right = newNode;
}

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

Now, let's go behind the scenes so that we can understand the code.