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
Hiring now
Get the Oracle interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question