😱 Most Developers Fail Here: Delete a Node from a BST in O(h) Without Recursion (Python Version)

Yes, this is one of those rare interview problems that looks simple… until you try it without recursion.

🎯 Delete a node from a Binary Search Tree
🧨 But with a twist:
✅ No recursion
✅ No stack
✅ No parent pointers
✅ Just O(1) extra space
✅ Must work in O(h) time

You read that right.

🧠 The Hidden Challenge
Most developers solve BST problems recursively. It’s clean. It’s elegant.
But what if you’re working in a memory-constrained system?
What if recursion is off-limits?

Now you're in real territory — the kind that makes or breaks you in system interviews.

This isn’t just about solving the problem.
It’s about solving it like a pro — with efficiency and control.

🔍 The Deletion Plan (Think Before You Code)
Here’s how you handle the three cases:

1. 🔵 Node not found
   Return root as-is.

2. 🟢 Node with no child
   Just remove it.

3. 🟡 Node with one child
   Replace the node with its child.

4. 🔴 Node with two children
   Here’s where it gets tricky:

Find the in-order successor (leftmost node in right subtree)

Copy its value into the node-to-delete

Delete the successor node

✅ All this without recursion

💡 Trick: Track Parent Iteratively
No parent pointers in the node? No problem.
We track the parent manually during search.

✅ Full Code — Python Version

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def deleteNode(root: TreeNode, key: int) -> TreeNode:
    parent = None
    curr = root

    # 1. Find the node to delete
    while curr and curr.val != key:
        parent = curr
        if key < curr.val:
            curr = curr.left
        else:
            curr = curr.right
    if not curr:
        return root  # Not found

    # 2. Handle deletion
    def delete_helper(node: TreeNode) -> TreeNode:
        if not node.left:
            return node.right
        if not node.right:
            return node.left

        # Find in-order successor
        succ = node.right
        succ_parent = node
        while succ.left:
            succ_parent = succ
            succ = succ.left

        node.val = succ.val
        if succ_parent.left == succ:
            succ_parent.left = succ.right
        else:
            succ_parent.right = succ.right

        return node

    new_child = delete_helper(curr)

    # 3. Fix parent link
    if not parent:
        return new_child  # root node deleted
    elif parent.left == curr:
        parent.left = new_child
    else:
        parent.right = new_child

    return root

🧪 Why This Stands Out
⚡ Runs in O(h) time

🧠 Uses just O(1) space

🚫 No recursion. No stack.

🔐 Safe for large BSTs

💼 Great fit for low-level system, embedded, or backend interviews

🤯 Bonus Thought
Most devs pass interviews with recursion.
Great devs impress with control.

If you understand how to solve tree problems iteratively, you’re operating on a different level.

💬 What Do You Think?
Have you ever tried deleting a node from a BST without recursion?

👇 Drop your version in the comments if:

You solved this differently

You want a JavaScript or C++ version

You’d love to see a visual walkthrough of this algorithm

🧲 Save This Post
This problem is a hidden gem in interviews.
Mastering it gives you a real edge.

✍️ Written with 💻 by Raj Guru Yadav
→ Building helpful tools, cracking deep problems, and sharing dev wisdom one post at a time.