🔥 Rare Coding Problem: Delete a Node from a BST in O(h) Time — Without Recursion

Hey dev

Yes, this is one of those rare interview-level questions that even seasoned developers trip over.

🧠 The Challenge
Problem:
Given the root of a BST and a key, delete the node in O(h) time and return the updated root.
✅ No recursion
✅ No stack
✅ No parent pointers
✅ Only O(1) auxiliary space

This problem isn't just about correctness — it's about space and time efficiency.

🔍 Why This Problem Is Rare
Most tutorials or interviews use a recursive solution for BST deletion.
But what if the call stack is not allowed? Or you're writing a system with strict memory limits?

Iterative deletion with parent tracking and in-order successor replacement makes this tricky.

⚙️ Solution Plan
Search for the node to delete while keeping track of its parent

If the node has:

No child → just remove it

One child → replace node with child

Two children → find in-order successor, replace value, then delete the successor

All of this is done iteratively.

✅ Full Code (C++)

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode *parent = NULL, *curr = root;

    // 1. Find the node to delete
    while (curr && curr->val != key) {
        parent = curr;
        curr = (key < curr->val) ? curr->left : curr->right;
    }
    if (!curr) return root; // Not found

    // 2. Handle deletion
    auto deleteHelper = [](TreeNode* node) -> TreeNode* {
        if (!node->left) return node->right;
        if (!node->right) return node->left;

        // Find inorder successor
        TreeNode* succ = node->right;
        TreeNode* succParent = node;
        while (succ->left) {
            succParent = succ;
            succ = succ->left;
        }

        node->val = succ->val;
        if (succParent->left == succ)
            succParent->left = succ->right;
        else
            succParent->right = succ->right;

        return node;
    };

    TreeNode* newChild = deleteHelper(curr);

    // 3. Update parent pointers
    if (!parent)
        return newChild;
    else if (parent->left == curr)
        parent->left = newChild;
    else
        parent->right = newChild;

    return root;
}

🧪 Why This is Awesome
⚡ O(h) time, where h = height of tree

🧠 O(1) space — no recursion or stack used

🔒 Safe for large BSTs with deep trees

💼 Perfect for low-level system interviews or when memory matters

🏁 Bonus Thought
Most developers solve BST problems recursively.
But going iterative gives you better control and makes you stand out in interviews.

Save this one. It might just help you crack your next system design or backend role.

💬 What Do You Think?
Have you ever implemented iterative BST deletion before?
👇 Let me know in the comments if you’ve solved this differently — or want the Python version too!

Comments

[Dotallio]

Really clean iterative approach - love seeing O(1) space solutions laid out like this. Would you mind sharing how you'd handle this in Python too?

[Rajguru Yadav]

Thank you so much! I'm really glad you liked the iterative approach and the O(1) space optimization 😊
Absolutely — I’ll be sharing the Python version soon in a follow-up article. I’ll make sure to keep it just as clean and efficient. Stay tuned!

[Nathan Tarbert]

This is extremely impressive. I always struggle to keep iterative BST problems clean like this

[Rajguru Yadav]

Thanks a lot! That truly means a lot 😊
Iterative BST problems can definitely get messy — I’ve struggled with that too. My focus here was on keeping the logic minimal and readable. I’m glad it came across that way!
Let me know if you'd like me to break down any part further — always happy to discuss more on this.