Building Threaded Binary Trees

March 2026 · 10 min read

Threaded BST Insertion

Inserting into a right-threaded BST is similar to standard BST insert, but we must carefully maintain threads when creating new nodes.

Algorithm

function threadedInsert(root, val):
if root == null: return newThreadedNode(val) parent = null, cur = root while cur != null: parent = cur if val < cur.val: if !cur.leftThread: cur = cur.left else: break // left is a thread, not a child else: if !cur.rightThread: cur = cur.right else: break // Now insert as child of parent node = newThreadedNode(val) if val < parent.val: node.left = parent.left // inherit predecessor thread node.right = parent // successor is parent parent.leftThread = false parent.left = node else: node.right = parent.right // inherit successor thread node.left = parent // predecessor is parent parent.rightThread = false parent.right = node

▶ Threaded BST Insertion Animation

Watch how inserting value 5 into a right-threaded BST maintains threads.

C++ Implementation

Why are leftThread and rightThread set to true initially?

In a threaded binary tree, each pointer serves one of two roles:

Child link (flag = false): the pointer leads to an actual child node.
Thread (flag = true): the pointer doesn't lead to a child — it stores a shortcut to the node's in-order predecessor (left) or successor (right).

When we first create a node, it's a leaf — it has no children at all. Neither left nor right point to real child nodes. Since both pointers are free of child duties, they are immediately available to serve as threads. That is exactly what the flags communicate: leftThread = true means "left is not a child link, it's a thread (or null)"; rightThread = true means the same for right.

Later, when an actual child is inserted beneath this node, the corresponding flag is flipped to false (e.g., parent->leftThread = false) to indicate "this pointer now leads to a real child, not a thread."

struct ThreadedNode {
    int val;
    ThreadedNode *left, *right;
    bool leftThread, rightThread;

    // Both flags start as true because a new node is a leaf:
    // it has no children, so both pointers are threads (not child links).
    ThreadedNode(int v) : val(v), left(nullptr), right(nullptr),
                          leftThread(true), rightThread(true) {}
};

void insert(ThreadedNode*& root, int val) {
    if (!root) { root = new ThreadedNode(val); return; }

    ThreadedNode* parent = nullptr;
    ThreadedNode* cur = root;

    while (cur) {
        parent = cur;
        if (val < cur->val) {
            if (!cur->leftThread) cur = cur->left;
            else break;
        } else {
            if (!cur->rightThread) cur = cur->right;
            else break;
        }
    }

    auto* node = new ThreadedNode(val);
    if (val < parent->val) {
        node->left = parent->left;      // inherit predecessor
        node->right = parent;            // successor = parent
        parent->leftThread = false;
        parent->left = node;
    } else {
        node->right = parent->right;     // inherit successor
        node->left = parent;             // predecessor = parent
        parent->rightThread = false;
        parent->right = node;
    }
}

Converting a Standard BST to Threaded

Given an existing BST, we can thread it by performing a reverse in-order traversal and linking null right pointers to successors:

void threadBST(TreeNode* node, TreeNode*& prev) {
    if (!node) return;
    threadBST(node->left, prev);

    if (prev && !prev->right) {
        prev->right = node;       // thread to successor
        prev->rightThread = true;
    }
    if (!node->left) {
        node->left = prev;        // thread to predecessor
        node->leftThread = true;
    }
    prev = node;

    threadBST(node->right, prev);
}

Deletion in Threaded BST

Deletion is trickier than standard BST because we must update threads. The three cases mirror standard BST deletion:

Leaf: Remove and update parent's pointer (restoring it to a thread).
One child: Replace with child, update threads of the child's subtree.
Two children: Find in-order successor, copy value, delete successor (which has at most one child).

Key difference from standard BST: When deleting a leaf, the parent's child pointer becomes a thread (set the thread flag to true, and point to the appropriate predecessor/successor).

Summary

Insertion requires inheriting threads from the parent and setting up new threads for the new node.
An existing BST can be converted to threaded in O(n) via in-order traversal.
Deletion must restore thread pointers when removing nodes.