Binary Search Tree (BST) Overview, Implementation, and Traversal in C

Before discussing binary trees, a brief introduction to trees is given: a tree consists of nodes, with a root node at the top and leaf nodes at the bottom; each node may have zero or more children.

A binary tree is a tree where each node has at most two children. A binary search tree (BST) is an ordered binary tree that satisfies three properties: the left subtree of any node contains only values smaller than the node’s value, the right subtree contains values greater than or equal to the node’s value, and both subtrees are themselves BSTs.

The article then defines the node structure in C:

typedef struct BTNode {
    int value;
    struct BTNode *left;
    struct BTNode *right;
} BTNode;

Basic operations are presented, each prefixed with bst for BST‑specific functions and plain names for generic binary‑tree functions.

Create node

/**
 * Create BTNode
 */
BTNode *newNode(int value) {
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}

BST insertion (recursive and iterative)

/**
 * BST insert (recursive)
 */
BTNode *bstInsert(BTNode *root, int value) {
    if (!root)
        return newNode(value);
    if (root->value > value)
        root->left = bstInsert(root->left, value);
    else
        root->right = bstInsert(root->right, value);
    return root;
}

/**
 * BST insert (iterative)
 */
BTNode *bstInsertIter(BTNode *root, int value) {
    BTNode *node = newNode(value);
    if (!root)
        return node;
    BTNode *current = root, *parent = NULL;
    while (current) {
        parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }
    if (parent->value >= value)
        parent->left = node;
    else
        parent->right = node;
    return root;
}

BST deletion

/**
 * BST delete node
 */
BTNode *bstDelete(BTNode *root, int value) {
    BTNode *parent = NULL, *current = root;
    BTNode *node = bstSearchIter(root, &parent, value);
    if (!node) {
        printf("Value not found\n");
        return root;
    }
    if (!node->left && !node->right) { // case 1: leaf
        if (node != root) {
            if (parent->left == node)
                parent->left = NULL;
            else
                parent->right = NULL;
        } else {
            root = NULL;
        }
        free(node);
    } else if (node->left && node->right) { // case 2: two children
        BTNode *predecessor = bstMax(node->left);
        bstDelete(root, predecessor->value);
        node->value = predecessor->value;
    } else { // case 3: one child
        BTNode *child = (node->left) ? node->left : node->right;
        if (node != root) {
            if (node == parent->left)
                parent->left = child;
            else
                parent->right = child;
        } else {
            root = child;
        }
        free(node);
    }
    return root;
}

BST search (recursive and iterative)

/**
 * BST search (recursive)
 */
BTNode *bstSearch(BTNode *root, int value) {
    if (!root) return NULL;
    if (root->value == value)
        return root;
    else if (root->value > value)
        return bstSearch(root->left, value);
    else
        return bstSearch(root->right, value);
}

/**
 * BST search (iterative)
 */
BTNode *bstSearchIter(BTNode *root, BTNode **parent, int value) {
    if (!root) return NULL;
    BTNode *current = root;
    while (current && current->value != value) {
        *parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }
    return current;
}

Find minimum and maximum nodes

/**
 * BST minimum node
 */
BTNode *bstMin(BTNode *root) {
    if (!root->left)
        return root;
    return bstMin(root->left);
}

/**
 * BST maximum node
 */
BTNode *bstMax(BTNode *root) {
    if (!root->right)
        return root;
    return bstMax(root->right);
}

Tree size and height

/**
 * Number of nodes in a binary tree
 */
int btSize(BTNode *root) {
    if (!root) return 0;
    return btSize(root->left) + btSize(root->right) + 1;
}

/**
 * Height of a binary tree
 */
int btHeight(BTNode *root) {
    if (!root) return 0;
    int leftHeight = btHeight(root->left);
    int rightHeight = btHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

Binary tree traversal

Recursive traversals

/**
 * Pre‑order traversal (recursive)
 */
void preOrder(BTNode *root) {
    if (!root) return;
    printf("%d ", root->value);
    preOrder(root->left);
    preOrder(root->right);
}

/**
 * In‑order traversal (recursive)
 */
void inOrder(BTNode *root) {
    if (!root) return;
    inOrder(root->left);
    printf("%d ", root->value);
    inOrder(root->right);
}

/**
 * Post‑order traversal (recursive)
 */
void postOrder(BTNode *root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->value);
}

/**
 * Level‑order traversal (recursive helper)
 */
void levelOrder(BTNode *root) {
    int h = btHeight(root);
    for (int level = 1; level <= h; ++level)
        levelOrderInLevel(root, level);
}

/**
 * Print nodes at a given level
 */
void levelOrderInLevel(BTNode *root, int level) {
    if (!root) return;
    if (level == 1) {
        printf("%d ", root->value);
        return;
    }
    levelOrderInLevel(root->left, level - 1);
    levelOrderInLevel(root->right, level - 1);
}

Non‑recursive traversals

/**
 * Pre‑order traversal (iterative)
 */
void preOrderIter(BTNode *root) {
    if (!root) return;
    int size = btSize(root);
    BTNodeStack *stack = stackNew(size);
    push(stack, root);
    while (!IS_EMPTY(stack)) {
        BTNode *node = pop(stack);
        printf("%d ", node->value);
        if (node->right) push(stack, node->right);
        if (node->left)  push(stack, node->left);
    }
    free(stack);
}

/**
 * In‑order traversal (iterative)
 */
void inOrderIter(BTNode *root) {
    if (!root) return;
    BTNodeStack *stack = stackNew(btSize(root));
    BTNode *current = root;
    while (current || !IS_EMPTY(stack)) {
        if (current) {
            push(stack, current);
            current = current->left;
        } else {
            BTNode *node = pop(stack);
            printf("%d ", node->value);
            current = node->right;
        }
    }
    free(stack);
}

/**
 * Post‑order traversal (iterative, single stack)
 */
void postOrderIter(BTNode *root) {
    BTNodeStack *stack = stackNew(btSize(root));
    BTNode *current = root;
    do {
        while (current) {
            if (current->right) push(stack, current->right);
            push(stack, current);
            current = current->left;
        }
        current = pop(stack);
        if (current->right && peek(stack) == current->right) {
            pop(stack);
            push(stack, current);
            current = current->right;
        } else {
            printf("%d ", current->value);
            current = NULL;
        }
    } while (!IS_EMPTY(stack));
}

/**
 * Post‑order traversal (iterative, two stacks)
 */
void postOrderIterWith2Stack(BTNode *root) {
    if (!root) return;
    BTNodeStack *stack = stackNew(btSize(root));
    BTNodeStack *output = stackNew(btSize(root));
    push(stack, root);
    while (!IS_EMPTY(stack)) {
        BTNode *node = pop(stack);
        push(output, node);
        if (node->left)  push(stack, node->left);
        if (node->right) push(stack, node->right);
    }
    while (!IS_EMPTY(output)) {
        BTNode *node = pop(output);
        printf("%d ", node->value);
    }
}

/**
 * Level‑order traversal (iterative using a queue)
 */
void levelOrderIter(BTNode *root) {
    if (!root) return;
    BTNodeQueue *queue = queueNew(btSize(root));
    enqueue(queue, root);
    while (1) {
        int nodeCount = QUEUE_SIZE(queue);
        if (nodeCount == 0) break;
        while (nodeCount > 0) {
            BTNode *node = dequeue(queue);
            printf("%d ", node->value);
            if (node->left)  enqueue(queue, node->left);
            if (node->right) enqueue(queue, node->right);
            nodeCount--;
        }
        printf("\n");
    }
}

The article concludes with references to external tutorials and notes that the code examples are intended for interview preparation and algorithm practice.