Convert Singly Linked List to height balanced BST

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

typedef struct node{
 int data;
 struct node *next;
 struct node *left;
}LNode;

LNode* newNode(int data){
 LNode *n = (LNode*)malloc(sizeof(LNode));
 n->data = data;
 n->next = NULL;
 n->left = NULL;
 return n;
}

void buildList(LNode **headRef){
 int i;
 for(i=7;i>0;i--){
  LNode *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(LNode *head){
    LNode *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(LNode *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}


LNode* buildBST(LNode* head){
        if(head == NULL || head->next == NULL) return head;
        LNode *root = NULL;
        LNode *slow = head;
        LNode *fast = head;
        LNode *prev = NULL;
        while(fast != NULL && fast->next != NULL){
                prev = slow;
                slow = slow->next;
                fast = fast->next->next;
        }

        root = slow;
        prev->next = NULL;
        root->left = buildBST(head);
        root->next = buildBST(slow->next);
        return root;
}

void preorder(LNode* root){
 if(root != NULL){
  printf("%d ",root->data);
  preorder(root->left);
  preorder(root->next);
 }
}

void inorder(LNode* root){
 if(root != NULL){
  inorder(root->left);
  printf("%d ",root->data);
  inorder(root->next);
 }
}

void postorder(LNode* root){
 if(root != NULL){
  postorder(root->left);
  postorder(root->next);
  printf("%d ",root->data);
 }
}

int main(){
 LNode *head = NULL;
 LNode *root = NULL;
 buildList(&head);
 display(head);
 root = buildBST(head);
 preorder(root);
 printf("\n");
 inorder(root);
 printf("\n");
 postorder(root);
// freeMem(head);
 return 0;
}

Inorder Traversal without using recursion

void inorder(Node* root){
if(root == NULL) return;
Node *temp = root;
push(temp);
while(!isempty()){
temp = temp->left;
while(temp != NULL){
push(temp);
temp = temp->left;
}
temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
temp = temp->right;
push(temp);
}
}
}

Preorder traversal of a BST, iteratively using a Stack

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

#define MAX 100

typedef struct node{
 int data;
 struct node* left;
 struct node* right;
}Node;

Node* s[MAX];
int top = -1;

Node* newNode(int data){
 Node* n = (Node *)malloc(sizeof(Node));
 n->data = data;
 n->left = NULL;
 n->right = NULL;
 return n;
}

void insertNode(Node* root,int data){
 if(data < root->data){
  if(root->left == NULL){
   root->left = newNode(data);
  } else {
   insertNode(root->left,data);
  }
 } else {
  if(root->right == NULL){
   root->right = newNode(data);
  } else {
   insertNode(root->right,data);
  }
 }
}

Node* createBST(Node **rootRef){
 Node *root = newNode(4);
 insertNode(root,2);
 insertNode(root,1);
 insertNode(root,3);
 insertNode(root,6);
 insertNode(root,5);
 insertNode(root,7);
 *rootRef = root;
}

void push(Node* n){
s[++top] = n;
}

Node* pop(){
return s[top--];
}

int isempty(){
return (top==-1);
}

void preorder(Node* root){
if(root == NULL){
return;
}
push(root);
while(!isempty()){
Node *temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
push(temp->right);
}
if(temp->left != NULL){
push(temp->left);
}
}
}

int main(){
 Node* root = NULL;
 createBST(&root);

 printf("\nPREORDER :\n");
 preorder(root);

 return 0;
}

Checking if a tree is a valid BST and BST Recursive Traversals

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

typedef struct node{
int data;
struct node* left;
struct node* right;
}Node;

Node* newNode(int data){
Node* n = (Node *)malloc(sizeof(Node));
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}

void insertNode(Node* root,int data){
if(data < root->data){
if(root->left == NULL){
root->left = newNode(data);
} else {
insertNode(root->left,data);
}
} else {
if(root->right == NULL){
root->right = newNode(data);
} else {
insertNode(root->right,data);
}
}
}

Node* createBST(Node **rootRef){
Node *root = newNode(4);
insertNode(root,2);
insertNode(root,6);
insertNode(root,1);
insertNode(root,3);
insertNode(root,5);
insertNode(root,7);
*rootRef = root;
}

void inorder(Node* root){
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}

void preorder(Node* root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

void postorder(Node* root){
if(root != NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}

int isBSTRecur(Node* root,int min,int max){
if(root == NULL){
return 1;
}
if(root->data > min && root->data < max){
return (isBSTRecur(root->left,min,root->data) && isBSTRecur(root->right,root->data,max));
} else {
return 0;
}
}

int isBST(Node* root){
return isBSTRecur(root,INT_MIN,INT_MAX);
}

int main(){
Node* root = NULL;
createBST(&root);
printf("INORDER :\n");
inorder(root);
printf("\nPREORDER :\n");
preorder(root);
printf("\nPOSTORDER :\n");
postorder(root);
if(isBST(root)){
printf("Valid BST");
} else {
printf("Invalid BST");
}
return 0;
}