Binary search tree programs

Binary Tree & BST Lab Record Programs


Q1A: Binary tree implementation using recursion (BST Insert)

struct node{ int data; struct node *left,*right; };

struct node* create(int val){
struct node* n=(struct node*)malloc(sizeof(struct node));
n->data=val; n->left=n->right=NULL; return n;
}

struct node* insert(struct node* root,int key){
if(root==NULL) return create(key);
if(key<root->data) root->left=insert(root->left,key);
else root->right=insert(root->right,key);
return root;
}




Q1B: Insert nodes level wise

struct node* insertLevel(struct node* root,int val){
if(root==NULL) return create(val);
struct node* q[100]; int f=0,r=0;
q[r++]=root;
while(f<r){
struct node* t=q[f++];
if(t->left==NULL){ t->left=create(val); return root;}
else q[r++]=t->left;
if(t->right==NULL){ t->right=create(val); return root;}
else q[r++]=t->right;
}
}




Q2A: Count number of non-leaf nodes

int countNonLeaf(struct node* root){
if(root==NULL || (root->left==NULL && root->right==NULL))
return 0;
return 1 + countNonLeaf(root->left) + countNonLeaf(root->right);
}




Q2B: BST operations (search, min, max, height)

struct node* search(struct node* root,int key){
if(root==NULL || root->data==key) return root;
if(key<root->data) return search(root->left,key);
else return search(root->right,key);
}

int findMin(struct node* root){
while(root->left) root=root->left;
return root->data;
}

int findMax(struct node* root){