Trees

BST Insert

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

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this C DSA implementation can be compared directly with the rest of the DSA track.

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); }

Complexity

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

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
binary search tree Values smaller than a node go left; larger values go right.