I’m trying to implement a simple AVL tree with insertions and deletions in C++ but my code isn’t getting the balance factor, or as some use, height, of each node correctly.

So, here is my code:

#include <iostream>
#include <stdlib.h>
#include <iomanip>

using namespace std;

struct Node {
    int key;

    struct Node *left, *right;
    int bf;
};

int height(Node *N) {
    if(N == NULL) return 0;

    return 1 + max(height(N->left), height(N->right));
}

int maximum(int a, int b) {
    return (a > b) ? a : b;
}

Node* newNode(int key) {
    Node* node = (struct Node*)malloc(sizeof(struct Node));

    node->key = key;
    node->left = node->right = NULL;
    node->bf = 0;

    return node;
}

Node *rightRotate(Node *y) {
    Node *root = y->left;
    Node *T2 = root->right;

    root->right = y;
    y->left = T2;

    y->bf = max(height(y->left), height(y->right)) + 1;
    root->bf = max(height(root->left), height(root->right)) + 1;

    return root;
}

Node *leftRotate(Node *x) {
    Node *root = x->right;
    Node *T2 = root->left;

    root->left = x;
    x->right = T2;

    x->bf = max(height(x->left), height(x->right)) + 1;
    root->bf = max(height(root->left), height(root->right)) + 1;

    return root;
}

void updateHeight(Node* node) {
    if(node != NULL) {
        node->bf = 1 + max(height(node->left), height(node->right));
    }
}

int getBalance(Node *N) {
    if(N == NULL) return 0;

    return height(N->left) - height(N->right);
}

Node* insert(Node* node, int key) {
    if(node == NULL) return(newNode(key));

    if(key < node->key) node->left = insert(node->left, key);
    else if(key > node->key) node->right = insert(node->right, key);
    else return node;

    node->bf = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if(balance > 1 && key < node->left->key) return rightRotate(node);
    if(balance < -1 && key > node->right->key) return leftRotate(node);
    if(balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    if(balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

Node* search(Node* root, int key) {
    if(!root) return NULL;

    if(root->key == key)
        return root;

    if(key < root->key) 
        return search(root->left, key);
    else 
        return search(root->right, key);
}

Node *minValueNode(Node *node) {
    Node *current = node;

    while(current->left != NULL) {
        current = current->left;
    }

    return current;
}

Node* deleteNode(struct Node* root, int key)
{
    if (root == NULL)
        return root;
 
    if ( key < root->key )
        root->left = deleteNode(root->left, key);
    else if( key > root->key )
        root->right = deleteNode(root->right, key);
    else
    {

        if( (root->left == NULL) || (root->right == NULL) )
        {
            struct Node *temp = root->left ? root->left :
                                             root->right;
 
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else 
             *root = *temp;
            free(temp);
        }
        else
        {
            struct Node* temp = minValueNode(root->right);

            root->key = temp->key;
 
            root->right = deleteNode(root->right, temp->key);
        }
    }
 
    if (root == NULL)
      return root;
 
    root->bf = 1 + max(height(root->left),
                           height(root->right));
 
    
    int balance = getBalance(root);
 
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);
 
    if (balance > 1 && getBalance(root->left) < 0)
    {
        root->left =  leftRotate(root->left);
        return rightRotate(root);
    }
 
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);
 
    if (balance < -1 && getBalance(root->right) > 0)
    {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
 
    return root;
}

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

int main() {
    Node *root = NULL;
    int n = 0;

    while(n >= 0) {
        cin >> n;
        if(n < 0) break;

        root = insert(root, n);
    }

    n = 0;

    while(n >= 0) {
        cin >> n;
        if(n < 0) break;

        Node* found = search(root, n);
        if(found == NULL) {
            root = insert(root, n);
        }
        else {
            root = deleteNode(root, n);
        }
    }

    int searched;
    cin >> searched;
    Node* found;

    found = search(root, searched);

    if(found == NULL) {
        cout << "Value not found"<< endl;
    }
    else {
        cout << found->bf << ",";
        cout << (found->left != NULL ? found->left->bf : 0) << ",";
        cout << (found->right != NULL ? found->right->bf : 0) << endl;
    }

    return 0;
}

I have some test cases for some help, like these:

6 4 3 2 1 -1
4 5 -1
6

It should output

0,0,0

But it outputs

1,0,0

If it helps, I have another input:

6 4 3 2 1 -1
4 5 -1
5

It should output

1,1,1

But mine outputs:

2,1,1

And I also have this one:

16 14 20 12 11 19 18 15 17 13 -1
14 19 15 20 -1
100

It should output

Value not found

But mine outputs:

2,0,0

The full code is supposed to have this kind of output:

The first line of the output contains the maximum height of the BST from its root node, followed by the height of the left and right subtrees from the root node. These values should be calculated considering only the tree built with the numbers from the first line of the input.
On the second line, the height of the searched node (line 3 of the input data) should be printed, followed by the height of its left and right subtrees. If this searched value is not found, “Value not found” should be displayed.

I still haven’t done this first part in my code because I’m trying to fix those height problems in it.