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:
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: Given 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 above BST. Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Example 2:
Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: The tree does not contain a node with value = 0.
Example 3:
Input: root = [], key = 0 Output: []
Constraints:
[0, 104].-105 <= Node.val <= 105root is a valid binary search tree.-105 <= key <= 105
Follow up: Could you solve it with time complexity O(height of tree)?
This approach involves traversing the tree recursively to find the node to be deleted. Once found, we handle it based on different cases: the node has no children, one child, or two children. For the two children case, replace the node with its inorder successor (minimum of the right subtree).
The function deleteNode recursively searches for the node with the provided key. If found, the node is deleted based on the number of its children. If the node has two children, it is replaced with its inorder successor.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h), where h is the height of the tree.
Space Complexity: O(h) due to recursion stack space.
This method uses an iterative approach with a stack to traverse and manipulate the binary search tree. By applying the concept of replacing with the inorder successor, this method ensures the tree's properties remain intact after deletion.
This iterative solution modifies pointers directly, allowing for efficient deletion by using a double pointer strategy for parent-child relationships.
C++
Java
Python
C#
JavaScript
Time Complexity: O(h), where h is tree height.
Space Complexity: O(1) since no additional data structures are used.
| Approach | Complexity |
|---|---|
| BST In-Place Deletion | Time Complexity: O(h), where h is the height of the tree. |
| Iterative Deletion with Stack | Time Complexity: O(h), where h is tree height. |
Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python • NeetCode • 296,166 views views
Watch 9 more video solutions →Practice Delete Node in a BST with our built-in code editor and test cases.
Practice on FleetCode