Binary Search Tree in C

01 Feb 2026 in Blog / Algorithms and Programming Languages , Tags: C

A complete guide to Solve the Binary Search Trees(BST) Problems in C & popular LeetCode BST problems

A guide to BST operations in C with LeetCode problem mappings

1. What is a Binary Search Tree?
2. Node Structure
3. Core BST Operations
4. Tree Traversals
5. BST Properties & Utilities
6. LeetCode Practice Problems
7. Full Working Code
8. Reference

1. What is a Binary Search Tree?

BST Property

graph TD
    A((50)) --> B((30))
    A --> C((70))
    B --> D((20))
    B --> E((40))
    C --> F((60))
    C --> G((80))

    style A fill:#6c5ce7,color:#fff
    style B fill:#00b894,color:#fff
    style C fill:#e17055,color:#fff
    style D fill:#00b894,color:#fff
    style E fill:#00b894,color:#fff
    style F fill:#e17055,color:#fff
    style G fill:#e17055,color:#fff

Every node follows one rule: left children are smaller and right children are larger. For example, 30 and 20 sit left of 50 (both smaller), while 70, 60, 80 sit right (all larger).

A Binary Search Tree (BST) is a binary tree where for every node:

All values in the left subtree are less than the node’s value
All values in the right subtree are greater than the node’s value
Both left and right subtrees are also BSTs

Example BST:

        50
       /  \
      30    70
     / \   / \
    20  40 60  80

Time Complexity

Operation	Average	Worst (skewed)	Space
Search	O(log n)	O(n)	O(1) iterative
Insert	O(log n)	O(n)	O(1) iterative
Delete	O(log n)	O(n)	O(1) iterative
Traversal	O(n)	O(n)	O(n)

This table shows BST operation complexities: average case is O(log n) for search, insert, and delete, but degrades to O(n) when the tree becomes skewed (like a linked list).

2. Node Structure

Memory Layout

 ┌──────────────────────────┐
 │       TreeNode           │
 ├──────────┬───────────────┤
 │ int val  │      50       │  ← data
 ├──────────┼───────────────┤
 │ left  ●──┼──→ [Node 30]  │  ← pointer to left child
 ├──────────┼───────────────┤
 │ right ●──┼──→ [Node 70]  │  ← pointer to right child
 └──────────┴───────────────┘
               │
        ┌──────┴──────┐
        ▼             ▼
   ┌─────────┐   ┌─────────┐
   │ val: 30 │   │ val: 70 │
   │ left: ∅ │   │ left: ∅ │
   │ right: ∅│   │ right: ∅│
   └─────────┘   └─────────┘

Each node is a C struct with three fields: int val stores the data, left and right are pointers to child nodes (or NULL if no child exists). Node 50 points left to 30 (smaller) and right to 70 (larger).

Required headers:

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

Node definition and constructor:

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

3. Core BST Operations

Insertion

Insertion Flow

Inserting 35 into this BST:

graph TD
    A((50)) -.->|"35 < 50 → go left"| B((30))
    B -.->|"35 > 30 → go right"| C((40))
    C -.->|"35 < 40 → go left"| D["✅ NULL → insert 35 here"]

    style A fill:#636e72,color:#fff
    style B fill:#636e72,color:#fff
    style C fill:#636e72,color:#fff
    style D fill:#00b894,color:#fff

Starting at the root, each comparison tells us exactly which direction to go. We keep moving down until we hit a NULL spot — that’s where the new node goes.

Iterative insertion:

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode* insert(TreeNode* root, int val) {
    TreeNode* newNode = createNode(val);
    if (root == NULL) return newNode;

    TreeNode* curr = root;
    TreeNode* parent = NULL;

    while (curr != NULL) {
        parent = curr;
        if (val < curr->val)
            curr = curr->left;
        else if (val > curr->val)
            curr = curr->right;
        else
            return root;  // duplicate — no insertion
    }

    if (val < parent->val)
        parent->left = newNode;
    else
        parent->right = newNode;

    return root;
}

int main() {
    TreeNode* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    printf("Tree built with 4 nodes\n");
    return 0;
}

Iterative insertion avoids recursion overhead and is preferred in performance-critical embedded systems and low-level C code.

Recursive insertion:

TreeNode* insertRecursive(TreeNode* root, int val) {
    if (root == NULL) return createNode(val);

    if (val < root->val)
        root->left = insertRecursive(root->left, val);
    else if (val > root->val)
        root->right = insertRecursive(root->right, val);

    return root;  // duplicate — unchanged
}

LeetCode Problems Using Insertion

Problem	What it asks (simplified)	Customization
701. Insert into a BST	Insert a value into a BST and return the root	Use the recursive insertion above directly.

Search

Search Flow

graph LR
    A["search(root, val)"] --> B{root == NULL?}
    B -->|Yes| C[Return NULL]
    B -->|No| D{"val == root->val?"}
    D -->|Yes| E[Found — return node]
    D -->|No| F{"val < root->val?"}
    F -->|Yes| G[Search left]
    F -->|No| H[Search right]

The search flow exploits BST ordering: at each node, the value tells us exactly which subtree to explore, eliminating half the tree at each step.

Iterative search:

TreeNode* search(TreeNode* root, int val) {
    while (root != NULL && root->val != val) {
        if (val < root->val)
            root = root->left;
        else
            root = root->right;
    }
    return root;  // NULL if not found
}

Recursive search:

TreeNode* searchRecursive(TreeNode* root, int val) {
    if (root == NULL || root->val == val)
        return root;

    if (val < root->val)
        return searchRecursive(root->left, val);
    else
        return searchRecursive(root->right, val);
}

LeetCode Problems Using Search

Problem	What it asks (simplified)	Customization
700. Search in a BST	Return the subtree rooted at the node with the target value	Use either iterative or recursive search above.

Find Min / Max

Operation	Logic	Code
Find Min	Go left until `left == NULL`	`while (root && root->left) root = root->left;`
Find Max	Go right until `right == NULL`	`while (root && root->right) root = root->right;`

The minimum value in a BST is always the leftmost node, and the maximum is always the rightmost. Both traverse a single path from root to leaf.

TreeNode* findMin(TreeNode* root) {
    while (root && root->left)
        root = root->left;
    return root;
}

TreeNode* findMax(TreeNode* root) {
    while (root && root->right)
        root = root->right;
    return root;
}

Deletion

Deletion Decision Flow

graph TD
    A["deleteNode(root, key)"] --> B{Found node?}
    B -->|No| C[Return NULL]
    B -->|Yes| D{How many children?}
    D -->|0 - Leaf| E[Free node, return NULL]
    D -->|1 child| F[Replace with child]
    D -->|2 children| G[Find inorder successor]
    G --> H["Copy successor's value"]
    H --> I["Delete successor from right subtree"]

Deletion has three cases: leaf nodes are simply removed, single-child nodes are replaced by their child, and two-child nodes use the inorder successor (smallest value in right subtree) as a replacement.

Three cases explained:

Case	Condition	Action	Example
Leaf	No children	Free node, return NULL	Delete 20 from tree
One child	Left or right is NULL	Bypass node with its child	Delete node with only right child
Two children	Both children exist	Replace with inorder successor, delete successor	Delete 30 (replace with 35)

This table summarizes the three deletion cases: each requires different handling based on the node’s child count.

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Case 1 & 2: No child or one child
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        // Case 3: Two children
        TreeNode* successor = findMin(root->right);
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

Deletion visualized (deleting 30):

  Case 3: Two children          After replacing with
        50                      inorder successor (35)
       /  \                          50
      30    70         →            /  \
     / \   / \                    35    70
    20  40 60  80                /  \  / \
       /                        20  40 60 80
      35

LeetCode Problems Using Deletion

Problem	What it asks (simplified)	Customization
450. Delete Node in a BST	Delete a value and return the updated root	Use the three-case deletion above directly.
669. Trim a BST	Remove all nodes outside range [low, high]	If `val < low`, return trimmed right subtree. If `val > high`, return trimmed left subtree.

4. Tree Traversals

Traversal Overview

graph TD
    A[Tree Traversals] --> B[DFS - Depth First]
    A --> C[BFS - Breadth First]
    B --> D["Inorder: L → Root → R"]
    B --> E["Preorder: Root → L → R"]
    B --> F["Postorder: L → R → Root"]
    C --> G["Level Order: Level by level"]
    D --> H["Sorted output for BST"]
    E --> I["Tree serialization"]
    F --> J["Safe deletion"]
    G --> K["Uses a Queue"]

Tree traversals are either depth-first (going deep before wide) or breadth-first (going wide before deep). Each DFS variant has specific use cases: inorder for sorting, preorder for copying, postorder for deletion.

Traversal Order Comparison

Traversal	Order	BST Use Case	Output for example tree
Inorder	Left → Root → Right	Sorted sequence	20 30 35 40 50 60 70 80
Preorder	Root → Left → Right	Serialize / copy tree	50 30 20 40 35 70 60 80
Postorder	Left → Right → Root	Safe free / delete	20 35 40 30 60 80 70 50
Level Order	Level by level	BFS analysis	50	30 70	20 40 60 80	35

This table compares the four traversal orders, their visit sequence, practical use cases, and the output produced when applied to the example BST.

Inorder (Left → Root → Right)

Produces a sorted sequence of values from a BST.

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

// Store inorder result in array (useful for many LeetCode problems)
void inorderToArray(TreeNode* root, int* arr, int* idx) {
    if (root == NULL) return;
    inorderToArray(root->left, arr, idx);
    arr[(*idx)++] = root->val;
    inorderToArray(root->right, arr, idx);
}

int main() {
    TreeNode* root = createNode(50);
    root->left = createNode(30);
    root->right = createNode(70);
    root->left->left = createNode(20);
    root->left->right = createNode(40);

    printf("Inorder: ");
    inorder(root);  // 20 30 40 50 70
    printf("\n");
    return 0;
}

Inorder traversal is the most important BST traversal — it produces a sorted sequence, which is the basis for problems like Kth Smallest, Validate BST, and finding minimum differences.

Preorder (Root → Left → Right)

Used to serialize or copy a tree. The root is visited first, making it ideal for reconstruction.

void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    preorder(root->left);
    preorder(root->right);
}

Postorder (Left → Right → Root)

Used to safely delete/free a tree — children are freed before the parent.

void postorder(TreeNode* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->val);
}

// Free entire tree using postorder
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

Always use postorder to free a tree in C. Freeing a parent before its children creates dangling pointers and memory leaks — a common mistake in manual memory management.

Level Order (BFS)

BFS Process

graph LR
    A[Enqueue root] --> B[Dequeue node]
    B --> C[Process node]
    C --> D{Has left child?}
    D -->|Yes| E[Enqueue left]
    D -->|No| F{Has right child?}
    E --> F
    F -->|Yes| G[Enqueue right]
    F -->|No| H{Queue empty?}
    G --> H
    H -->|No| B
    H -->|Yes| I[Done]

Level order traversal uses a queue: enqueue the root, then repeatedly dequeue a node, process it, and enqueue its children. This visits all nodes level by level from top to bottom.

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// Simple queue for BFS
typedef struct {
    TreeNode* data[10000];
    int front, rear;
} Queue;

void initQueue(Queue* q) { q->front = 0; q->rear = 0; }
void enqueue(Queue* q, TreeNode* node) { q->data[q->rear++] = node; }
TreeNode* dequeue(Queue* q) { return q->data[q->front++]; }
bool isEmpty(Queue* q) { return q->front == q->rear; }

void levelOrder(TreeNode* root) {
    if (root == NULL) return;

    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    while (!isEmpty(&q)) {
        int size = q.rear - q.front;  // nodes at current level

        for (int i = 0; i < size; i++) {
            TreeNode* node = dequeue(&q);
            printf("%d ", node->val);

            if (node->left)  enqueue(&q, node->left);
            if (node->right) enqueue(&q, node->right);
        }
        printf("\n");  // new line per level
    }
}

Level order traversal is essential for problems that require processing nodes level-by-level, such as finding the width of a tree, right-side view, or zigzag traversal.

LeetCode Problems Using Traversals

Problem	What it asks (simplified)	Customization
94. Binary Tree Inorder Traversal	Return inorder sequence as array	Use `inorderToArray` helper, return the array.
144. Binary Tree Preorder Traversal	Return preorder sequence as array	Visit root first, then left, then right into array.
145. Binary Tree Postorder Traversal	Return postorder sequence as array	Visit left, right, then root into array.
102. Binary Tree Level Order Traversal	Return values grouped by level	Use BFS with queue, track level size.
107. Level Order Traversal II	Level order bottom to top	Same as 102, then reverse the result array.

5. BST Properties & Utilities

Height of Tree

graph TD
    A["height(root)"] --> B{root == NULL?}
    B -->|Yes| C["Return -1"]
    B -->|No| D["leftH = height(left)"]
    D --> E["rightH = height(right)"]
    E --> F["Return 1 + max(leftH, rightH)"]

Height is computed recursively: the height of an empty tree is -1, and each node adds 1 to the maximum height of its subtrees.

int height(TreeNode* root) {
    if (root == NULL) return -1;  // -1 for edges, 0 for nodes

    int leftH  = height(root->left);
    int rightH = height(root->right);

    return 1 + (leftH > rightH ? leftH : rightH);
}

Example:

        50          height = 3
       /  \
      30    70      height = 2
     / \   / \
    20  40 60  80   height = 1
       /
      35            height = 0

Count Nodes

int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

Validate BST

Validation Strategy

graph TD
    A["isValidBST(root, min, max)"] --> B{root == NULL?}
    B -->|Yes| C["Return true"]
    B -->|No| D{"val <= min OR val >= max?"}
    D -->|Yes| E["Return false — violates BST"]
    D -->|No| F["Check left with (min, root->val)"]
    F --> G["Check right with (root->val, max)"]
    G --> H["Return left AND right"]

Validation uses a min/max range that narrows at each level: left children must be less than the parent, right children must be greater. This catches the common mistake of only checking immediate parent.

#include <stdbool.h>
#include <limits.h>

bool isValidBSTHelper(TreeNode* root, long min, long max) {
    if (root == NULL) return true;

    if (root->val <= min || root->val >= max)
        return false;

    return isValidBSTHelper(root->left, min, root->val) &&
           isValidBSTHelper(root->right, root->val, max);
}

bool isValidBST(TreeNode* root) {
    return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}

Why just checking parent is wrong:

        5
       / \
      1    6      ← Looks valid at each parent
          / \
         3   7    ← 3 < 5 — violates BST property!

The range-based approach catches this: node 3 would need to be in range (5, 6), but 3 < 5, so it fails.

Lowest Common Ancestor

LCA Decision Flow

graph TD
    A["LCA(root, p, q)"] --> B{"p < root AND q < root?"}
    B -->|Yes| C["Both in left → go left"]
    B -->|No| D{"p > root AND q > root?"}
    D -->|Yes| E["Both in right → go right"]
    D -->|No| F["Split point = LCA!"]

In a BST, the LCA is the first node where the two target values diverge into different subtrees. This makes it O(log n) instead of the O(n) general tree approach.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root != NULL) {
        if (p->val < root->val && q->val < root->val)
            root = root->left;       // both in left subtree
        else if (p->val > root->val && q->val > root->val)
            root = root->right;      // both in right subtree
        else
            return root;             // split point = LCA
    }
    return NULL;
}

Kth Smallest Element

Use inorder traversal (sorted order) and count down to k.

void kthSmallestHelper(TreeNode* root, int k, int* count, int* result) {
    if (root == NULL || *count >= k) return;

    kthSmallestHelper(root->left, k, count, result);

    (*count)++;
    if (*count == k) {
        *result = root->val;
        return;
    }

    kthSmallestHelper(root->right, k, count, result);
}

int kthSmallest(TreeNode* root, int k) {
    int count = 0, result = -1;
    kthSmallestHelper(root, k, &count, &result);
    return result;
}

Example (k=3):

Inorder: 20, 30, [35], 40, 50, 60, 70, 80
                   ↑
              3rd smallest = 35

LeetCode Problems Using BST Properties

Problem	What it asks (simplified)	Customization
98. Validate BST	Check if tree is a valid BST	Use min/max range validation. Do NOT just check parent — check global range.
104. Maximum Depth	Return height of the tree	Recursively compute `1 + max(left, right)`. Base case: NULL returns 0 (or -1 for edge count).
110. Balanced Binary Tree	Check if height difference ≤ 1 at every node	Modify height function to return -1 if unbalanced, propagate up.
222. Count Complete Tree Nodes	Count nodes in complete tree	Simple recursion `1 + count(left) + count(right)`. Optimized: compare left/right heights.
230. Kth Smallest	Find kth smallest value in BST	Inorder traversal with counter. Stop early when count reaches k.
235. LCA of BST	Find lowest common ancestor	Exploit BST ordering: follow split point where p and q diverge.
530. Min Absolute Difference	Find minimum difference between any two nodes	Inorder traversal, track previous value, compute min diff at each step.

6. LeetCode Practice Problems

Problem 1: Convert Sorted Array to BST

Build a height-balanced BST from a sorted array by always picking the middle element as root.

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

TreeNode* sortedArrayToBST(int* nums, int left, int right) {
    if (left > right) return NULL;

    int mid = left + (right - left) / 2;
    TreeNode* root = createNode(nums[mid]);
    root->left  = sortedArrayToBST(nums, left, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, right);
    return root;
}

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

int main() {
    int nums[] = {-10, -3, 0, 5, 9};
    int n = 5;
    TreeNode* root = sortedArrayToBST(nums, 0, n - 1);
    printf("Inorder: ");
    inorder(root);  // -10 -3 0 5 9
    printf("\n");
    return 0;
}

Process:

Array: [-10, -3, 0, 5, 9]
                ↓
Mid = 0 (index 2)         →  Root = 0
Left half:  [-10, -3]     →  Left subtree
Right half: [5, 9]        →  Right subtree

Result:
        0
       / \
     -3    9
     /    /
   -10   5

This technique guarantees a balanced tree (height difference ≤ 1). It’s a divide-and-conquer approach used in database index construction and balanced tree initialization.

Problem 2: Invert Binary Tree

Swap left and right children at every node recursively.

TreeNode* invertTree(TreeNode* root) {
    if (root == NULL) return NULL;

    TreeNode* temp = root->left;
    root->left  = invertTree(root->right);
    root->right = invertTree(temp);
    return root;
}

Process:

Before:         After:
    4              4
   / \            / \
  2    7   →    7    2
 / \  / \      / \  / \
1   3 6   9   9   6 3   1

Tree inversion is a classic recursion problem famously associated with Homebrew creator Max Howell’s Google interview. It tests understanding of tree structure manipulation and recursive thinking.

Problem 3: Two Sum IV (BST)

Flatten BST to sorted array via inorder, then use two pointers.

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

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void inorderToArray(TreeNode* root, int* arr, int* idx) {
    if (root == NULL) return;
    inorderToArray(root->left, arr, idx);
    arr[(*idx)++] = root->val;
    inorderToArray(root->right, arr, idx);
}

bool findTarget(TreeNode* root, int k) {
    int arr[10001];
    int idx = 0;
    inorderToArray(root, arr, &idx);

    int lo = 0, hi = idx - 1;
    while (lo < hi) {
        int sum = arr[lo] + arr[hi];
        if (sum == k) return true;
        else if (sum < k) lo++;
        else hi--;
    }
    return false;
}

Example (k=9):

Inorder: [2, 3, 4, 6, 7]
          ↑            ↑     2+7=9 ✓ Found!
         lo           hi

This combines BST inorder traversal with the classic two-pointer technique. The sorted property of inorder output makes two-pointer search optimal at O(n) time and O(n) space.

Problem 4: Trim a BST

Remove all nodes outside the range [low, high].

TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (root == NULL) return NULL;

    if (root->val < low)
        return trimBST(root->right, low, high);
    if (root->val > high)
        return trimBST(root->left, low, high);

    root->left  = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

Process (trim [1, 3]):

Before:         After:
    3              3
   / \            /
  0    4   →    2
   \           /
    2         1
   /
  1

Trimming uses BST ordering: if a node is below the range, all its left children are too, so we only keep the right subtree (and vice versa). This makes it efficient — no need to check every node twice.

Problem 5: Minimum Absolute Difference

Find the minimum difference between any two node values in a BST.

#include <stdio.h>
#include <limits.h>

void minDiffHelper(TreeNode* root, int* prev, int* minDiff) {
    if (root == NULL) return;

    minDiffHelper(root->left, prev, minDiff);

    if (*prev != -1) {
        int diff = root->val - *prev;
        if (diff < *minDiff) *minDiff = diff;
    }
    *prev = root->val;

    minDiffHelper(root->right, prev, minDiff);
}

int getMinimumDifference(TreeNode* root) {
    int prev = -1, minDiff = INT_MAX;
    minDiffHelper(root, &prev, &minDiff);
    return minDiff;
}