Declan Mitchell
Declan Mitchell

Reputation: 31

Removing Root Node from a BST?

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

Answers (0)

Related Questions