bst.c

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "bst.h"

///*****Functions from bst.c of Exercise 1*****

Node* leftMost(Node* rightNode) {

    Node* temp = rightNode;

    while (temp && temp -> left != NULL)
        temp = temp -> left;

    return temp;
}

Node* insertNode(Node *N, int value) {

    if (N == NULL) {
        N = malloc(sizeof(struct Node));
        N -> data = value;
        N -> left = NULL;
        N -> right = NULL;
    } else if (N -> data < value) {
        N -> right = insertNode(N -> right, value);
    } else if (N -> data > value)
        N -> left = insertNode(N -> left, value);

    return N;
}

Node* deleteNode(Node* N, int value) {

    if (N == NULL) return N;

    if (value > N -> data) {
        N -> right = deleteNode(N -> right, value);
    } else if (value < N -> data) {
        N -> left = deleteNode(N -> left, value);
    } else {
        if (N -> left == NULL) {
            Node *temp = N -> right;
            free(N);
            return temp;
        } else if (N -> right == NULL) {
            Node *temp = N -> left;
            free(N);
            return temp;
        }

        Node* temp = leftMost(N -> right);
        N -> data = temp -> data;
        N -> right = deleteNode(N -> right, temp -> data);
    }

    return N;
}

void printSubtree(Node *N) {

    if (N != NULL) {
        printSubtree(N -> left);
        printf("%d\n", N -> data);
        printSubtree(N -> right);
    }
}

int countNodes(Node *N) {

    if (N == NULL)
        return 0;

    return countNodes(N -> left) + countNodes(N -> right) + 1;
}

Node* freeSubtree(Node *N) {

    if (N == NULL) return N;

    if (N -> left != NULL) freeSubtree(N -> left);
    if (N -> right != NULL) freeSubtree(N -> right);

    free(N);
    return NULL;

}

///********************************************

Node* makeBalance(Node *N, int arr[], int leftBorder, int rightBorder) {
    if (leftBorder > rightBorder)
        return NULL;

    int middle = (leftBorder + rightBorder)/2;
    N = insertNode(N, arr[middle]);

    N -> left = makeBalance(N -> left, arr, leftBorder, middle-1);
    N -> right = makeBalance(N -> right, arr, middle+1, rightBorder);

    return N;
}

int treeArray(Node* N, int arr[], int i) {
    if(N == NULL)
        return i;

    if(N -> left != NULL)
          i = treeArray(N -> left, arr, i);

    arr[i] = N -> data;
    i++;

    if(N -> right != NULL)
        i = treeArray(N -> right, arr, i);

    return i;
}

int bstLength(Node* N) {
    if (N != NULL)
        return bstLength(N -> left) + 1 + bstLength(N -> right);

    return 0;
}

int sumSubtree(Node *N) {
    if (N != NULL)
        return sumSubtree(N -> left) + (N -> data) + sumSubtree(N -> right);

    return 0;
}

Node* balanceTree(Node* N) {
    if (N == NULL)
        return N;

    int size = bstLength(N);
    int *arr = NULL;
    arr = malloc(size * sizeof(int));

    treeArray(N, arr, 0);

    Node* nRoot = NULL;
    nRoot = makeBalance(nRoot, arr, 0, size-1);
    return nRoot;
}