Threaded Tree Patterns & Practice

Approach

If the node is right-threaded (rightThread == true), the right pointer is the successor, just return it directly. That's the whole point of threading.

If the node has a real right child (rightThread == false), the successor is the leftmost node in the right subtree. Go right once, then keep going left until you can't.

ThreadedNode* inorderSuccessor(ThreadedNode* node) {
    // Case 1: Thread exists — follow it directly
    if (node->rightThread)
        return node->right;  // O(1)

    // Case 2: Has right child — find leftmost in right subtree
    ThreadedNode* succ = node->right;
    while (succ->left && !succ->leftThread)
        succ = succ->left;
    return succ;
}

Why O(1) Amortized?

Case 1 is O(1). Case 2 could be O(h) for a single call, but if you traverse the entire tree by repeatedly calling inorderSuccessor, each edge is visited at most twice total. Over n calls, the total work is O(n), so amortized O(1) per call.

Complexity

Time	O(1) amortized
Space	O(1)

Approach: Reverse In-order with Previous Pointer

The trick is to do a reverse in-order traversal (right, root, left). This visits nodes from largest to smallest. We maintain a prev pointer to the previously visited node. When we visit a node, if its right child is null, we thread it to prev (which is its in-order successor, since we're going in reverse).

void convertToThreaded(ThreadedNode* root) {
    ThreadedNode* prev = nullptr;

    std::function<void(ThreadedNode*)> reverseInorder =
        [&](ThreadedNode* node) {
        if (!node) return;

        reverseInorder(node->right);  // visit right first

        // If right is null, thread it to the in-order successor
        if (!node->right) {
            node->right = prev;       // thread to successor
            node->rightThread = true;
        } else {
            node->rightThread = false;
        }

        prev = node;                  // I'm the prev for the next node

        reverseInorder(node->left);   // visit left
    };

    reverseInorder(root);
}

Why Reverse In-order?

In reverse in-order (right → root → left), the previously visited node is always the in-order successor of the current node. So when we encounter a null right pointer, we already have the correct successor in prev.

If we used forward in-order, prev would be the predecessor, useful for left-threading, but not right-threading.

Walkthrough

For a BST [4, 2, 6, 1, 3, 5, 7], in reverse in-order we visit: 7, 6, 5, 4, 3, 2, 1.

• Visit 7: right is null, prev is null → thread to null (no successor). Set prev = 7.
• Visit 6: right is 7 (real child) → not threaded. Set prev = 6.
• Visit 5: right is null → thread to prev = 6. Set prev = 5.
• Visit 4: right is 6 (real child) → not threaded. Set prev = 4.
• Visit 3: right is null → thread to prev = 4. Set prev = 3.
• Visit 2: right is 3 (real child) → not threaded. Set prev = 2.
• Visit 1: right is null → thread to prev = 2. Set prev = 1.

Result: 1→2, 3→4, 5→6, 7→null. Correct!

Complexity

Time	O(n) — visit each node once
Space	O(h) — recursion stack

Approach: In-order Traversal with Validation

Do a standard in-order traversal (using a stack, since the tree might be incorrectly threaded and we can't trust the threads). Track the previous node. For each node:

• If rightThread is true, check that right points to the actual in-order successor.
• If leftThread is true, check that left points to the previous node (in-order predecessor).

bool isValidThreading(ThreadedNode* root) {
    // Collect in-order sequence using stack (don't trust threads)
    std::vector<ThreadedNode*> inorder;
    std::stack<ThreadedNode*> stk;
    auto* cur = root;
    while (cur || !stk.empty()) {
        while (cur && !cur->leftThread) {
            stk.push(cur);
            cur = cur->left;
        }
        if (cur && cur->leftThread) stk.push(cur);
        if (stk.empty()) break;
        cur = stk.top(); stk.pop();
        inorder.push_back(cur);
        cur = cur->rightThread ? nullptr : cur->right;
    }

    // Validate each thread
    for (int i = 0; i < (int)inorder.size(); i++) {
        auto* node = inorder[i];
        if (node->rightThread) {
            auto* expected = (i + 1 < (int)inorder.size())
                             ? inorder[i + 1] : nullptr;
            if (node->right != expected) return false;
        }
        if (node->leftThread) {
            auto* expected = (i - 1 >= 0)
                             ? inorder[i - 1] : nullptr;
            if (node->left != expected) return false;
        }
    }
    return true;
}

Complexity

Time	O(n)
Space	O(n) for the inorder array

Approach

Deletion in a threaded BST follows standard BST deletion with extra thread maintenance. The three cases:

Case 1: Leaf Node

The simplest case. If the leaf is a left child, its parent's left becomes a thread to the leaf's in-order predecessor. If the leaf is a right child, its parent's right becomes a thread to the leaf's in-order successor (which the leaf was threaded to).

Case 2: One Child

Replace the node with its child. But we must also fix the thread of the child's predecessor or successor. Specifically, the deleted node's in-order predecessor's thread needs to point to the deleted node's successor (if it was threaded to the deleted node).

Case 3: Two Children

Replace with in-order successor (which, in a threaded tree, we can find in O(1) if the node is threaded, or O(h) otherwise). Then delete the successor from its original position (which reduces to Case 1 or Case 2).

ThreadedNode* deleteNode(ThreadedNode* root, int key) {
    ThreadedNode* parent = nullptr;
    ThreadedNode* cur = root;
    bool found = false;

    // Search for the node
    while (cur) {
        if (key == cur->val) { found = true; break; }
        parent = cur;
        if (key < cur->val) {
            if (!cur->leftThread) cur = cur->left;
            else break;
        } else {
            if (!cur->rightThread) cur = cur->right;
            else break;
        }
    }
    if (!found) return root;

    // Case 3: Two children — replace with inorder successor
    if (!cur->leftThread && cur->left &&
        !cur->rightThread && cur->right) {
        // Find in-order successor
        ThreadedNode* succParent = cur;
        ThreadedNode* succ = cur->right;
        while (!succ->leftThread && succ->left) {
            succParent = succ;
            succ = succ->left;
        }
        cur->val = succ->val;  // copy value
        // Now delete succ (which has at most one child)
        parent = succParent;
        cur = succ;
    }

    // Cases 1 & 2: Leaf or one child
    // Find the in-order predecessor and successor for thread fixup
    ThreadedNode* pred = cur->leftThread ? cur->left : nullptr;
    ThreadedNode* succ = cur->rightThread ? cur->right : nullptr;

    ThreadedNode* child = nullptr;
    if (!cur->leftThread && cur->left)
        child = cur->left;
    else if (!cur->rightThread && cur->right)
        child = cur->right;

    // Fix the predecessor's thread
    if (pred) {
        // pred was threaded to cur; now thread to cur's successor
        if (pred->rightThread && pred->right == cur)
            pred->right = succ;
    }

    // Fix the successor's thread
    if (succ) {
        // succ's left thread might point to cur
        if (succ->leftThread && succ->left == cur)
            succ->left = pred;
    }

    // Reattach child to parent
    if (!parent) return child;  // deleting root
    if (parent->left == cur) {
        if (!child) {
            parent->leftThread = true;
            parent->left = pred;  // thread to predecessor
        } else {
            parent->left = child;
        }
    } else {
        if (!child) {
            parent->rightThread = true;
            parent->right = succ;  // thread to successor
        } else {
            parent->right = child;
        }
    }

    delete cur;
    return root;
}

The Key Insight

The extra complexity compared to standard BST deletion is thread maintenance. When you remove a node, up to two threads may need updating: the predecessor's right thread and the successor's left thread. Always find the predecessor and successor before removing the node.

Complexity

Time	O(h) — search + successor finding
Space	O(1)

Approach

This is where threaded trees shine. In a standard BST, finding the kth smallest requires O(h) stack space for in-order traversal. In a threaded BST, we can do the entire traversal with O(1) space, just follow the threading!

1. Start at the leftmost node (smallest element).
2. Use the inorderSuccessor function from Problem 1 to step through nodes one by one.
3. Count to k.

int kthSmallest(ThreadedNode* root, int k) {
    // Go to the leftmost (smallest) node
    ThreadedNode* cur = root;
    while (cur->left && !cur->leftThread)
        cur = cur->left;

    // Walk through k nodes using threading
    int count = 0;
    while (cur) {
        count++;
        if (count == k) return cur->val;

        // Move to in-order successor
        if (cur->rightThread) {
            cur = cur->right;  // follow thread
        } else {
            // Go to leftmost node in right subtree
            cur = cur->right;
            while (cur && cur->left && !cur->leftThread)
                cur = cur->left;
        }
    }
    return -1;  // k is larger than tree size
}

Why This Matters

Compare with the standard BST approach:

	Standard BST	Threaded BST
Time	O(h + k)	O(h + k) — same
Space	O(h) — stack	O(1) — no stack!

The time is the same, but we eliminated all auxiliary space. This is exactly the kind of improvement threaded trees are built for.

Approach

The standard threaded traversal starts at the leftmost node and follows right threads. The reverse version starts at the rightmost node and follows left threads (which point to in-order predecessors in a double-threaded tree).

void reverseInorder(ThreadedNode* root) {
    // Go to the rightmost (largest) node
    ThreadedNode* cur = root;
    while (cur->right && !cur->rightThread)
        cur = cur->right;

    // Traverse using left threads
    while (cur) {
        visit(cur);  // process current node

        // Move to in-order predecessor
        if (cur->leftThread) {
            cur = cur->left;  // follow left thread to predecessor
        } else if (cur->left) {
            // Go to rightmost node in left subtree
            cur = cur->left;
            while (cur->right && !cur->rightThread)
                cur = cur->right;
        } else {
            cur = nullptr;  // no predecessor — we're done
        }
    }
}

Why Double Threading Helps

Without left threads, reverse traversal would require a stack (to go back to the parent). Double threading gives us predecessor links for free, enabling both forward and reverse traversal with O(1) space.

Complexity

Time	O(n)
Space	O(1)