Solving Intuit SDE 2 Interview Question: Delete a Node from BST

Hey there! I'm an Software Engineer 2 at Intuit (ex-Microsoft), and in this blog post, I'll be discussing a problem that's commonly asked in coding interviews for the SDE 2 role at Intuit.

This question revolves around the concept of Binary Search Trees (BSTs). It is focused on deleting a node with a given value from a Binary Search Tree.

Let’s dive in!

Problem Statement

Given a Binary Search Tree and a node value X. Delete the node with the given value X from the BST. If no node with value x exists, then do not make any change.

Example 1:

Example 2:

Your Task: You don't need to read input or print anything. Your task is to complete the function deleteNode() which takes two arguments. The first being the root of the tree, and an integer 'X' denoting the node value to be deleted from the BST. Return the root of the BST after deleting the node with value X. Do not make any update if there's no node with value X present in the BST.

Note: The generated output will be the inorder traversal of the modified tree.

Expected Time Complexity: O(Height of the BST).

Expected Auxiliary Space: O(Height of the BST).

Constraints: 1 <= N <= 105

(Source: GeeksforGeeks)

Solution

To solve this problem, we need to follow the steps for deleting a node from a Binary Search Tree (BST). The deletion process in a BST involves three cases:

1️⃣ Node to be deleted is a leaf node: Simply remove the node from the tree.

2️⃣ Node to be deleted has one child: Remove the node and replace it with its child.

3️⃣ Node to be deleted has two children: Find the inorder successor (smallest in the right subtree) or inorder predecessor (largest in the left subtree) of the node, copy its value to the node, and delete the inorder successor or predecessor.

Here's a step-by-step approach to implement the deleteNode() function:

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

def deleteNode(root, X):
    if not root:
        return root

    # If the value to be deleted is smaller than the root's value,
    # then it lies in the left subtree
    if X < root.val:
        root.left = deleteNode(root.left, X)

    # If the value to be deleted is greater than the root's value,
    # then it lies in the right subtree
    elif X > root.val:
        root.right = deleteNode(root.right, X)

    # If value is same as root's value, then this is the node to be deleted
    else:
        # Node with only one child or no child
        if not root.left:
            temp = root.right
            root = None
            return temp
        elif not root.right:
            temp = root.left
            root = None
            return temp

        # Node with two children: Get the inorder successor (smallest in the right subtree)
        temp = minValueNode(root.right)

        # Copy the inorder successor's content to this node
        root.val = temp.val

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.val)

    return root

def minValueNode(node):
    current = node
    # Loop down to find the leftmost leaf
    while current.left is not None:
        current = current.left
    return current

Explanation:

👉 If the node to be deleted is a leaf node or has one child, we simply remove the node or replace it with its single child.

👉 If the node to be deleted has two children, we need to find the inorder successor (the smallest value in the right subtree) or the inorder predecessor (the largest value in the left subtree).

In this implementation, we find the inorder successor by finding the leftmost node in the right subtree.

👉 After finding the inorder successor, we copy its value to the node to be deleted and then delete the inorder successor, which will now have at most one child, making it easier to delete.

This approach ensures that the BST properties are maintained after the deletion.

The expected time complexity is O(Height of the BST) because in the worst case, we might have to travel from the root to the leaf node.

The expected auxiliary space is also O(Height of the BST) due to the recursion stack.

*****

That's it for this problem! I hope you found the solution and explanations helpful.

If you're someone who's actively preparing for coding interviews, particularly for companies like Intuit or Microsoft, feel free to reach out to me.

I'd be happy to discuss more coding problems, share interview experiences, or provide any guidance I can based on my own experiences.

Click here to book a 1:1 free trial session!