Delete a Node from a Binary Search Tree
Updated
Problem statement
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
keyis 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) → TreeNodeExamples
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]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]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]No node has the value 5, so the tree is returned unchanged.
Constraints
- The tree has between
0and500nodes. 0 <= Node.val <= 10^5- All node values are distinct, and
rootis a valid binary search tree. 0 <= key <= 10^5- The tree does not have to be balanced. It can be a single chain of
500nodes.
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