A solution to determine whether the sequence of integers is the sequential traversal result of a binary search tree

Enter an array of integers to determine if the array is the result of a sequential traversal of a binary search tree.
If true, otherwise false.
For example, enter 5, 7, 6, 9, 11, 10, 8, because this sequence of integers is the result of the sequential traversal of the following tree.
      8
    / \
  6     10
/ \       / \
5   7, 9, 11
So return true.
If you type 7, 4, 6, 5, none of the tree's subsequent traversals result in this sequence, so false is returned.
This problem has been used on the Internet recursive simple judgment solution.
Personal solution: First, the corresponding middle sequence of the sequence is obtained, and then whether the sequence is ordered from small to large order is determined.
Compared with: The time complexity is the same, the space of N is increased, but the corresponding middle order sequence can be obtained.
The following is the code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LEN 100
int seq[LEN + 1] = {0};
int *mid = NULL;
int pos = 1;
void getmid(int start, int end);
int check(int num);
int main()
{
 int val;
 int num;
 int ret;
 int i;
 printf("input the sequence, end it with '-9999': ");

 num = 1;
 scanf("%d", &val);
 while(val != -9999)
 {
  seq[num] = val;
  num ++;
  scanf("%d", &val);
 }
 num--;
 mid = (int *)malloc((num + 1) * sizeof(int));
 if(mid == NULL)
 {
  printf("malloc failed.n");
  exit(1);
 }
 memset(mid, 0, num + 1);
 getmid(1, num);

 printf("mid: ");
 for(i = 1; i< num +1; i++)
 {
  printf("%d ", mid[i]);
 }
 printf("n");
 ret = check(num);
 if(ret == -1)
 {
  printf("no.n");
 }
 else
 {
  printf("yesn");
 }
 return 0;
}
void getmid(int start, int end)
{
 int flag;
 if(start > end)
 {
  return;
 }
 if(start == end)
 {
  mid[pos] = seq[end];
  pos ++;
  return;
 }
 int par;
 par = start;
 flag = 0;
 while(par < end)
 {
  if(seq[par] > seq[end])
  {
   flag = 1;
   getmid(start, par - 1);
   mid[pos] = seq[end];
   pos ++;   
   getmid(par, end - 1);
   break;
  }
  par ++;
 }
 if(!flag)
 {
  getmid(start, end-1);
  mid[pos] = seq[end];
  pos ++;
 }
}
int check(int num)
{
 int i;

 for(i = 1; i < num; i++)
 {
  if(mid[i] > mid[i+1])
  {
   return -1;
  }
 }
 return 0;
}