Reputation: 31
I build my tree in main with a for loop adding nodes 1-15, removing say 5 or 15 work fine, i think my problem lies in removing the root. It wont follow pre-order when I call it after removing 1, i think this has something to do with the head pointer in tree? other functions removed my main to be able to post as well as hasLeft and hasRight.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
struct node {
struct node * right;
struct node * left;
int val;
};
struct binarySearchTree{
struct node * head;
};
struct node* treeSearch(int k, struct node * v){
if(v->left == NULL && v->right == NULL){
return v;
}
if(k < v->val){
return treeSearch(k, v->left);
}else if( k > v->val){
return treeSearch(k, v->right);
}else{
return v;
}
}
struct node * insert(int k, struct node * v){
if(v == NULL){
struct node * newnode = malloc(sizeof(struct node));
if(!newnode){
return NULL; //failed allocation
}
newnode->val = k;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
if(k < v->val){
v->left = insert(k, v->left);
}else if(k > v->val){
v->right = insert(k, v->right);
}
return v;
}
struct node * findMin(struct node * root){
struct node * cur = root;
while (cur->left != NULL){
cur = cur->left;
}
return cur;
}
struct node * removeNode(int k, struct node * root){
struct node * temp;
if(root == NULL){
return NULL;
}
if(k < root->val){
root->left = removeNode(k, root->left);
}else if(k > root->val){
root->right = removeNode(k, root->right);
}else{
if(root->left == NULL && root->right == NULL){
free(root);
return NULL;
}else if(root->left == NULL){
temp = root->right;
free(root);
return temp;
}else if(root->right == NULL){
temp = root->left;
free(root);
return temp;
}else{
struct node * minNode = findMin(root->right);
root->val = minNode->val;
removeNode(minNode->val, root->right);
return root;
}
}
}
struct binarySearchTree * createBinaryTree(){
struct binarySearchTree * tree = malloc(sizeof(struct binarySearchTree));
if(!tree){
printf("failed\n");
return NULL;
}
tree->head = NULL;
return tree;
}
void inorder(struct node * v){
if(hasLeft(v)){
inorder(v->left);
}
printf("%d ", v->val);
if(hasRight(v)){
inorder(v->right);
}
}
Upvotes: 1
Views: 29