PPractick

The problem

The leaderboard BST must also support removing a score while staying a valid BST. Deletion has three cases:

1. A leaf simply disappears.
2. A node with one child is replaced by that child.
3. A node with two children takes the value of its inorder successor (the smallest key in its right subtree), and that successor, which has no left child, is then deleted from the right subtree.

Example: BST [5, 3, 6, 2, 4, null, 7], delete 3 → [5, 4, 6, 2, null, null, 7].

Function signature

TreeNode* deleteNode(TreeNode* root, int key);  // returns the new root; no-op if key is absent

Test cases

Input (tree, key)	Output (level order)	Explanation
([5, 3, 6, 2, 4, null, 7], 3)	[5, 4, 6, 2, null, null, 7]	Two children: replaced by successor 4
([5, 3, 6, 2, 4, null, 7], 5)	[6, 3, 7, 2, 4]	The root is replaced by 6
([5, 3, 6, 2, 4, null, 7], 0)	[5, 3, 6, 2, 4, null, 7]	Key absent
([1], 1)	[]	The last node
([], 0)	[]

(Confirm: keys are distinct; any valid resulting BST is accepted, and the successor-replacement result is shown.)

How interviewers phrase it

• "Given a root node reference of a BST and a key, delete the node with the given key and return the root" (LeetCode 450).

Clarifying questions to ask

1. What if the key doesn't exist? (Return the tree unchanged.)
2. May I copy values between nodes, or must nodes be relinked? (Copying is fine here.)
3. Must the height stay small? (No balancing required.)

Follow-ups to expect

1. "Why the inorder successor?"
2. "Why is deleting the successor easy?"
3. "Could you use the predecessor instead?"
4. "How would you relink instead of copying values?"
5. "Complexity?"

Related questions

• Insert a given node in BST Medium
• Check if a tree is a BST or not Medium
• LCA in BST Medium
• Construct a BST from a preorder traversal Medium
• Search in a Binary Search Tree Easy
• Floor and Ceil in a BST Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in