FastPrepDelete a Node from a Binary Search Tree
Problems/Delete a Node from a Binary Search Tree

Delete a Node from a Binary Search Tree

NVIDIA logoNVIDIA● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a first-round interview for an NVIDIA AI infrastructure internship. One of the two coding tasks was removing a value from a binary search tree.

The report gives no input format or limits. It gives no rule for which value replaces a deleted node that has two children. Here the tree holds 0 to 500 distinct values, each from 0 to 10^5, and the key is also from 0 to 10^5. A missing key leaves the tree unchanged. A node with two children takes the smallest value from its right subtree. You get and return the tree in level order.

Our version is about 85% the same as the reported question.

You are given the root of a binary search tree and an integer key. Delete the node whose value is key, if there is one, and return the root of the updated tree.

In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. The tree must still be a binary search tree after the deletion. Follow these rules so that there is only one correct result:

  • If key is not in the tree, return the tree unchanged.
  • If the node has no children, remove it.
  • If the node has one child, that child takes the node's place.
  • If the node has two children, replace the node's value with the smallest value in its right subtree, then remove the node that held that smallest value. That node has no left child, so its right child, if any, takes its place.

Trees are written in level order, with null for a missing child. An empty tree is [].

Function

deleteNode(root: TreeNode, key: int) → TreeNode

Examples

Example 1

root = [8,3,10,1,6,null,14,null,null,4,7]key = 6return = [8,3,10,1,7,null,14,null,null,4]
root
8316471014
Removed
→
return
831741014
Moved or new

The node with value 6 has two children, 4 and 7. The smallest value in its right subtree is 7, so 6 is replaced by 7, and the old node 7 (a leaf) is removed. The tree becomes 8 with children 3 and 10; 3 has children 1 and 7; 7 keeps the left child 4; 10 keeps the right child 14.

Example 2

root = [8,3,10,1,6,null,14,null,null,4,7]key = 10return = [8,3,14,1,6,null,null,null,null,4,7]
root
8316471014
Removed
→
return
83164714
Moved or new

The node with value 10 has only one child, 14. That child takes its place under 8, and the rest of the tree does not change.

Example 3

root = [2,1,3]key = 5return = [2,1,3]
root
213
→
return
213

No node has the value 5, so the tree is returned unchanged.

Constraints

  • The tree has between 0 and 500 nodes.
  • 0 <= Node.val <= 10^5
  • All node values are distinct, and root is a valid binary search tree.
  • 0 <= key <= 10^5
  • The tree does not have to be balanced. It can be a single chain of 500 nodes.

More NVIDIA Phone Screen questions

  • Summarize Server Healthcheck LogsPHONE SCREEN · Seen Oct 2026
  • Hash Partition OffsetsPHONE SCREEN · Seen Oct 2026
  • Filter Paginated Medical RecordsPHONE SCREEN · Seen Oct 2026
  • Least Frequently Used CachePHONE SCREEN · Seen Oct 2026
  • Parallel String Counts with a Custom Hash TablePHONE SCREEN · Seen Oct 2026
  • Simulate a Reference-Counted Smart PointerPHONE SCREEN · Seen Aug 2026
  • Streaming Top-K Frequent ElementsPHONE SCREEN · Seen Aug 2026
  • Merge Multiple Sorted StreamsPHONE SCREEN · Seen Aug 2026
  • Linked List Palindrome in Constant SpacePHONE SCREEN · Seen Aug 2026
  • LRU Key-Value Cache OperationsPHONE SCREEN · Seen Aug 2026

Similar questions at other companies

  • Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
  • Construct a Binary Tree from Preorder and InordereBay · PHONE SCREENeBay interview questions
  • Filter Data with Composable PredicatesCoreWeave · PHONE SCREEN
  • Trim a Binary Search Tree to a RangeGoogle · PHONE SCREENGoogle interview questions
  • Count Uni-Valued SubtreesAmazon · PHONE SCREEN
  • Reconstruct a BST from PreorderLyft · PHONE SCREENLyft interview questions
  • Rebuild a Binary Tree From Two WalksAdobe · PHONE SCREENAdobe interview questions
  • AVL Insertion and RotationsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
  • Delete Node in a BSTBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Build an Expression Tree from PostfixPeopleStrong · PHONE SCREENPeopleStrong interview questions

Interview reports that mention this question

  • NVIDIA DevOps, QA and Infra Intern Interviews: 12 Experiences

NVIDIA interview experiences

  • NVIDIA Ignite Internship OA Experience
  • NVIDIA Software Intern Interview Questions: 9 Experiences
  • NVIDIA Ignite SWE Intern OA Questions: 6 Experiences
All NVIDIA interview questionsSee NVIDIA hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // Write your code here.
    }
}
Checking account…