Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

Algorithm

Basic Implementation

basic.c 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node { int value; struct Node* left; struct Node* right; } Node;
Node* node_new(int value, Node* left, Node* right) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = value; node->left = left; node->right = right; return node;
}
void append(char* out, const char* text) { strcat(out, text); }
void render(Node* node, char* out) {
    char buf[16];
    if (node == NULL) { append(out, "_"); return; }
    sprintf(buf, "%d", node->value); append(out, buf);
    if (node->left != NULL || node->right != NULL) {
        append(out, "("); render(node->left, out); append(out, ","); render(node->right, out); append(out, ")");
    }
}
Node* sample_tree(void) {
    return node_new(4, node_new(2, node_new(1, NULL, NULL), node_new(3, NULL, NULL)),
                       node_new(6, node_new(5, NULL, NULL), node_new(7, NULL, NULL)));
}
void print_list(int* values, int n) {
    printf("[");
    for (int i = 0; i < n; i++) { if (i) printf(", "); printf("%d", values[i]); }
    printf("]\n");
}
Node* insert(Node* root, int value) { if (!root) return node_new(value, NULL, NULL); if (value < root->value) root->left = insert(root->left, value); else root->right = insert(root->right, value); return root; }
int main(void) { int values[] = {4, 2, 6, 1, 3, 5, 7}; Node* root = NULL; for (int i = 0; i < 7; i++) root = insert(root, values[i]); char out[128] = ""; render(root, out); printf("%s\n", out); }

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • C defines typedef struct Node { int value; struct Node* left; struct Node* right; } Node, so child links are raw pointers that are either NULL or point at heap-allocated nodes.
  • node_new calls malloc(sizeof(Node)), writes value, left, and right, and returns the owning pointer. This checked executable does not free the allocated nodes.
  • insert(Node* root, int value) returns the updated subtree root: NULL creates a new node, smaller values assign root->left = insert(...), and all other values assign root->right = insert(...), so duplicates would go right.
  • main starts with Node* root = NULL and inserts the stack array values {4, 2, 6, 1, 3, 5, 7}; the returned pointer is assigned back to root on each pass.
  • The trace records tree states 4, 4(2,_), 4(2,6), 4(2(1,_),6), 4(2(1,3),6), 4(2(1,3),6(5,_)), and 4(2(1,3),6(5,7)).
  • render(Node* node, char* out) writes into stack buffer char out[128] with sprintf and strcat, using _ for NULL children. The replay also shows sorted inserts forming 1(_,2(_,3(_,4))), a height-4 unbalanced chain.
binary search tree Values smaller than a node go left; larger values go right.