Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \2 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7
Approach #1: C++.[recursive]
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* deleteNode(TreeNode* root, int key) { if (root == nullptr) return nullptr; if (root->val < key) root->right = deleteNode(root->right, key); else if (root->val > key) root->left = deleteNode(root->left, key); else { if (root->left == nullptr) return root->right; else if (root->right == nullptr) return root->left; else { TreeNode* minNode = findMinNode(root->right); root->val = minNode->val; root->right = deleteNode(root->right, root->val); } } return root; } private: TreeNode* findMinNode(TreeNode* node) { if (node->left != nullptr) findMinNode(node->left); return node; }};
Approach #2: Java.[recursive]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; if (root.val > key) root.left = deleteNode(root.left, key); else if (root.val < key) root.right = deleteNode(root.right, key); else { if (root.left == null) return root.right; else if (root.right == null) return root.left; else { TreeNode minNode = findMinNode(root.right); root.val = minNode.val; root.right = deleteNode(root.right, root.val); } } return root; } private TreeNode findMinNode (TreeNode root) { while (root.left != null) { root = root.left; } return root; }}
Appraoch #3: Python.[Iterator]
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ cur = root pre = None while cur is not None and cur.val is not key: pre = cur if key < cur.val: cur = cur.left elif key > cur.val: cur = cur.right if pre is None: return self.deleteRootNode(cur) if pre.left == cur: pre.left = self.deleteRootNode(cur) else: pre.right = self.deleteRootNode(cur) return root def deleteRootNode(self, node): if node is None: return None if node.left is None: return node.right if node.right is None: return node.left nextNode = node.right pre = None while nextNode.left is not None: pre = nextNode nextNode = nextNode.left nextNode.left = node.left if node.right is not nextNode: pre.left = nextNode.right nextNode.right = node.right return nextNode