If the sub-tree S1 has the height of 1, what is the minimum number of nodes and maximum number of nodes in the subtree S1? Count the intermediate nodes and the leaf nodes in the sub-tree S1. code example

Example: b tree in c

// Searching a key on a B-tree in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct btreeNode
{
  int val[MAX + 1], count;
  struct btreeNode *link[MAX + 1];
};

struct btreeNode *root;

struct btreeNode *createNode(int val, struct btreeNode *child)
{
  struct btreeNode *newNode;
  newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
  newNode->val[1] = val;
  newNode->count = 1;
  newNode->link[0] = root;
  newNode->link[1] = child;
  return newNode;
}

void addValToNode(int val, int pos, struct btreeNode *node,
          struct btreeNode *child)
{
  int j = node->count;
  while (j > pos)
  {
    node->val[j + 1] = node->val[j];
    node->link[j + 1] = node->link[j];
    j--;
  }
  node->val[j + 1] = val;
  node->link[j + 1] = child;
  node->count++;
}

void splitNode(int val, int *pval, int pos, struct btreeNode *node,
         struct btreeNode *child, struct btreeNode **newNode)
{
  int median, j;

  if (pos > MIN)
    median = MIN + 1;
  else
    median = MIN;

  *newNode = (struct btreeNode *)malloc(sizeof(struct btreeNode));
  j = median + 1;
  while (j <= MAX)
  {
    (*newNode)->val[j - median] = node->val[j];
    (*newNode)->link[j - median] = node->link[j];
    j++;
  }
  node->count = median;
  (*newNode)->count = MAX - median;

  if (pos <= MIN)
  {
    addValToNode(val, pos, node, child);
  }
  else
  {
    addValToNode(val, pos - median, *newNode, child);
  }
  *pval = node->val[node->count];
  (*newNode)->link[0] = node->link[node->count];
  node->count--;
}

int setValueInNode(int val, int *pval,
           struct btreeNode *node, struct btreeNode **child)
{

  int pos;
  if (!node)
  {
    *pval = val;
    *child = NULL;
    return 1;
  }

  if (val < node->val[1])
  {
    pos = 0;
  }
  else
  {
    for (pos = node->count;
       (val < node->val[pos] && pos > 1); pos--)
      ;
    if (val == node->val[pos])
    {
      printf("Duplicates not allowed\n");
      return 0;
    }
  }
  if (setValueInNode(val, pval, node->link[pos], child))
  {
    if (node->count < MAX)
    {
      addValToNode(*pval, pos, node, *child);
    }
    else
    {
      splitNode(*pval, pval, pos, node, *child, child);
      return 1;
    }
  }
  return 0;
}

void insert(int val)
{
  int flag, i;
  struct btreeNode *child;

  flag = setValueInNode(val, &i, root, &child);
  if (flag)
    root = createNode(i, child);
}

void search(int val, int *pos, struct btreeNode *myNode)
{
  if (!myNode)
  {
    return;
  }

  if (val < myNode->val[1])
  {
    *pos = 0;
  }
  else
  {
    for (*pos = myNode->count;
       (val < myNode->val[*pos] && *pos > 1); (*pos)--)
      ;
    if (val == myNode->val[*pos])
    {
      printf("%d is found", val);
      return;
    }
  }
  search(val, pos, myNode->link[*pos]);

  return;
}

void traversal(struct btreeNode *myNode)
{
  int i;
  if (myNode)
  {
    for (i = 0; i < myNode->count; i++)
    {
      traversal(myNode->link[i]);
      printf("%d ", myNode->val[i + 1]);
    }
    traversal(myNode->link[i]);
  }
}

int main()
{
  int val, ch;

  insert(8);
  insert(9);
  insert(10);
  insert(11);
  insert(15);
  insert(16);
  insert(17);
  insert(18);
  insert(20);
  insert(23);

  traversal(root);

  printf("\n");
  search(11, &ch, root);
}