Delete a node in BST
OracleThe problem
Given the root node of a binary search tree (BST) and a value key. Return the root node of the BST after the deletion of the node with the given key value.
Note: As there can be many correct answers, the compiler returns true if the answer is correct, otherwise false.
Input : root = [5, 3, 6, 2, 4, null, 7] , key = 3 Output : [5, 4, 6, 2, null, null, 7] Explanation : Below is image of the original BST
Below is image where the node 3 is deleted
Input : root = [5, 3, 6, 2, 4, null, 7] , key = 0 Output : [5, 3, 6, 2, 4, null, 7] Explanation : The tree does not have node with value 0.
Input : root = [5, 3, 6, 2, 4, null, 7] , key = 5
- 1 <= Number of nodes <= 104
- -108 <= Node.val <= 108
- All values in tree are unique.
- -108 <= key <= 108
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def deleteNode(self, root, key):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
deleteNode(root, key) {
//your code goes here
}
}csharp
// Definition for a binary tree node.
// public class TreeNode {
// public int val;
// public TreeNode left;
// public TreeNode right;
// public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
public class Solution {
public TreeNode DeleteNode(TreeNode root, int key) {
}
}go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
// your code goes here
}Stuck? Show a way to structure it+
- 01Search for the key using BST ordering.
- 02Return the non-null child for zero- or one-child deletion.
- 03For two children, replace using inorder successor or predecessor.
- 04Delete the replacement value from its original subtree.
Reference answer
Then expect these follow-ups
When would you choose predecessor rather than successor?
Tests: symmetry
How can deletion be implemented iteratively?
Tests: parent pointers
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question