Binary tree operations

After choosing a representation, you implement operations: query the tree (search, traversals) and change its shape (attach new nodes, delete nodes). This lesson uses linked nodes (struct Node with left / right)—the same idea introduced on Tree representation, spelled out in full here. Follow with Binary tree using array and Binary tree using linked list for specialized storage lessons. Ordered search trees (BST) come later—see Binary search tree.

1) Search

In a general binary tree there is no ordering guarantee, so “find value v” is typically a DFS or BFS walk until the first match—O(n) in the worst case. A BST can do better for search when you only go left/right by comparison; that is covered later.

2) Attach (insert under a known parent)

A simple API is: locate the parent by value, then attach a new node on an empty left or right slot. If the slot is already taken, the operation fails (or you choose another policy). This matches how many textbook demos build fixed shapes.

Heap “insert” at the next level-order position is different—that is specialized array logic; here we insert relative to an explicit parent pointer.

3) Delete — three structural cases

Removing a node x must preserve the rest of the tree as a binary tree (each node still has ≤ 2 children).

Other valid rules exist (e.g. successor from the right subtree). Duplicates as keys complicate “delete value” unless you define which occurrence to remove—the demo assumes values are unique for clarity.

4) Arrays vs pointers for updates

In an array-based tree, deleting or inserting in the middle often means shifting many entries or leaving holes—usually awkward. Pointer trees only relink a few edges, which is why mutable binary trees in C are usually pointer-based.

5) Complete C program (linked tree)

The program demonstrates find, attachLeft / attachRight, and deleteByValue with the three cases. Download binary-tree-operations-demo.c and compile with gcc -std=c11 binary-tree-operations-demo.c -o tree_ops_demo.

// Binary tree operations demo (linked representation).
// Covers search, attach child under a known parent value, delete by value (3 cases).
// Duplicate values are not supported as keys (delete removes one occurrence predictably via DFS order).
// Compile: gcc -std=c11 binary-tree-operations-demo.c -o tree_ops_demo

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;

static Node *createNode(int data) {
    Node *n = (Node *)malloc(sizeof(Node));
    if (!n) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = n->right = NULL;
    return n;
}

static void freeTree(Node *root) {
    if (!root) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

// DFS search first matching value
Node *find(Node *root, int value) {
    if (!root) {
        return NULL;
    }
    if (root->data == value) {
        return root;
    }
    Node *t = find(root->left, value);
    return t ? t : find(root->right, value);
}

static void inorder(Node *root) {
    if (!root) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

static Node *maxRightmostInSubtree(Node *sub) {
    if (!sub) {
        return NULL;
    }
    Node *cur = sub;
    while (cur->right) {
        cur = cur->right;
    }
    return cur;
}

// Remove first node with key found in subtree rooted at root; returns new subtree root.
static Node *deleteFound(Node *root);

Node *deleteByValue(Node *root, int key) {
    if (!root) {
        return NULL;
    }
    if (root->data == key) {
        return deleteFound(root);
    }
    root->left = deleteByValue(root->left, key);
    root->right = deleteByValue(root->right, key);
    return root;
}

static Node *deleteFound(Node *root) {
    if (!root->left && !root->right) {
        free(root);
        return NULL;
    }
    if (!root->left) {
        Node *t = root->right;
        free(root);
        return t;
    }
    if (!root->right) {
        Node *t = root->left;
        free(root);
        return t;
    }
    // Two children: replace with value from rightmost node in left subtree, then delete that node.
    Node *pred = maxRightmostInSubtree(root->left);
    root->data = pred->data;
    root->left = deleteByValue(root->left, pred->data);
    return root;
}

bool attachLeft(Node *root, int parentValue, int newValue) {
    Node *p = find(root, parentValue);
    if (!p || p->left) {
        return false;
    }
    p->left = createNode(newValue);
    return true;
}

bool attachRight(Node *root, int parentValue, int newValue) {
    Node *p = find(root, parentValue);
    if (!p || p->right) {
        return false;
    }
    p->right = createNode(newValue);
    return true;
}

// Build sample tree: root 10; children 5,15; leaves 3,7 and 20 under 15.

static Node *buildSample(void) {
    Node *r = createNode(10);
    r->left = createNode(5);
    r->right = createNode(15);
    r->left->left = createNode(3);
    r->left->right = createNode(7);
    r->right->right = createNode(20);
    return r;
}

int main(void) {
    printf("=== Binary tree operations (linked) ===\n\n");

    Node *root = buildSample();
    printf("Initial inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Search --\n");
    int keys[] = {7, 99};
    for (size_t i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
        Node *h = find(root, keys[i]);
        printf("find(%d): %s\n", keys[i], h ? "found" : "not found");
    }

    printf("\n-- Attach child (only if slot empty) --\n");
    if (attachLeft(root, 15, 12)) {
        printf("Attached 12 as left child of 15\n");
    } else {
        printf("attachLeft(15,12) failed (missing parent or left busy)\n");
    }
    printf("Inorder after attach: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete leaf (20) --\n");
    root = deleteByValue(root, 20);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete one-child node (15 has only left child 12; delete 15 lifts 12 to parent) --\n");
    root = deleteByValue(root, 15);
    printf("Inorder: ");
    inorder(root);
    printf("\n");

    printf("\n-- Delete node with two children (root 10) --\n");
    printf("Before: ");
    inorder(root);
    printf("\n");
    root = deleteByValue(root, 10);
    printf("After removing 10: ");
    inorder(root);
    printf("\n");

    printf("\nFreeing remaining tree...\n");
    freeTree(root);
    printf("Done.\n");
    return 0;
}

6) Typical time costs (general binary tree)

7) What’s next

In this track: specialize storage with Binary tree using array, then Binary tree using linked list (broader demos of the linked model). When keys follow BST ordering, continue to Binary search tree and Binary search tree operations.