Binary search tree operations

A binary search tree (BST) maintains an ordering rule for every subtree: keys smaller than the current key are stored in the left subtree, and keys greater than it in the right subtree. This tutorial assumes unique integer keys; other applications must choose a consistent duplicate-key policy and comparator.

Search and insertion

At a node, compare the target with the current key. A match finishes the search. Otherwise descend left or right until you find the key or an empty position. Insertion follows the same path but creates a node at the first empty child. The correctness argument depends on applying the ordering rule to every descendant, not only the immediate children.

C#

C# | BST.cs

public sealed class Node
{
    public int Key;
    public Node? Left, Right;
    public Node(int key) => Key = key;
}

static bool Contains(Node? root, int key)
{
    while (root is not null)
    {
        if (key == root.Key) return true;
        root = key < root.Key ? root.Left : root.Right;
    }
    return false;
}

static Node Insert(Node? root, int key)
{
    if (root is null) return new Node(key);
    if (key < root.Key) root.Left = Insert(root.Left, key);
    else if (key > root.Key) root.Right = Insert(root.Right, key);
    return root; // duplicates ignored
}

C++

C++ | BST.cpp

#include <memory>
struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};

bool contains(const Node* root, int key) {
    while (root) {
        if (root->key == key) return true;
        root = key < root->key ? root->left.get() : root->right.get();
    }
    return false;
}

void insert(std::unique_ptr<Node>& root, int key) {
    if (!root) { root = std::make_unique<Node>(key); return; }
    if (key < root->key) insert(root->left, key);
    else if (key > root->key) insert(root->right, key);
    // duplicate keys are ignored
}

Deletion needs three cases

1. Leaf: remove the node.
2. One child: replace it with its single child.
3. Two children: replace the node’s key with its inorder successor, the smallest key in its right subtree, then delete the original successor node. The predecessor from the left subtree is another valid approach.

Do not simply detach a two-child node or you will lose part of its tree. In C++, ownership and pointer lifetime require special care; in C#, existing external references to nodes may also influence application behavior.

Deletion code

The following implementations reuse the Node type from the insertion example. In C#, capture the returned root because removing the root may replace it. In C++, passing std::unique_ptr<Node>& lets the function update ownership safely; callers must not retain pointers to nodes that were deleted.

C#

C# | BSTDeletion.cs

// Call: root = Remove(root, key); the root may change.
static Node? Remove(Node? root, int key)
{
    if (root is null) return null;
    if (key < root.Key) root.Left = Remove(root.Left, key);
    else if (key > root.Key) root.Right = Remove(root.Right, key);
    else
    {
        if (root.Left is null) return root.Right;
        if (root.Right is null) return root.Left;
        Node successor = root.Right;
        while (successor.Left is not null) successor = successor.Left;
        root.Key = successor.Key;
        root.Right = Remove(root.Right, successor.Key);
    }
    return root;
}

C++

C++ | BSTDeletion.cpp

#include <memory>
// Uses the Node type declared in the insertion example above.
void erase(std::unique_ptr<Node>& root, int key) {
    if (!root) return;
    if (key < root->key) erase(root->left, key);
    else if (key > root->key) erase(root->right, key);
    else {
        if (!root->left) { root = std::move(root->right); return; }
        if (!root->right) { root = std::move(root->left); return; }
        Node* successor = root->right.get();
        while (successor->left) successor = successor->left.get();
        root->key = successor->key;
        erase(root->right, successor->key);
    }
}

Cost depends on height

Search, insert and delete follow at most one root-to-leaf path plus constant work per level, so they take O(h) time for tree height h. A balanced tree gives O(log n) height. A sorted insertion sequence into a naive BST can create a chain with O(n) height. Recursive implementations use O(h) call stack; iterative lookup can use O(1) additional space.

Try it: Insert 8, 3, 10, 1, 6, 14, 4, 7 by hand, search for 7, then delete 3. Check that an inorder traversal remains sorted.

Reference: W3Schools binary search trees.