Insert

Lesson 9 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

insert starts as an ordinary binary search tree insert: walk down comparing values, go left or right, and place the new node where a null slot is found (ignore duplicates). The AVL part happens on the way back up: after placing the node, every ancestor on the path recomputes its height and checks its balance factor.

If a node becomes unbalanced, which side is heavy and where the new value landed together decide which of the four cases applies: left-left and right-right need a single rotation, while left-right and right-left need two, an inner rotation to straighten the zig-zag followed by the outer one.

Challenge

Medium

Write a method insert(value) on AVLTree (a recursive helper is the cleanest way). Insert value like a normal BST, ignoring it if already present. On the way back up, recompute each node's height and balance factor, and if a node is unbalanced, apply the matching rotation (or pair of rotations) before returning up the call stack.

Try it yourself

#include <stdio.h>
#include <string.h>
#include "avltree.h"

static void preorderValues(Node* node, int* vals, int* count) {
    if (node == NULL) {
        return;
    }
    vals[(*count)++] = node->value;
    preorderValues(node->left, vals, count);
    preorderValues(node->right, vals, count);
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
            int vals[10000];
            int count = 0;
            preorderValues(tree->root, vals, &count);
            for (int i = 0; i < count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%d", vals[i]);
            }
            printf("\n");
        }
        if (parsed >= 1 && strcmp(cmd, "height") == 0) {
            printf("%d\n", AVLTree_getHeight(tree, tree->root));
        }
    }
    return 0;
}