Delete Node In A BST Leetcode Problem 450 [Python Solution]
In this blog post, we'll dive into the "Delete Node in a Binary Search Tree" problem, a medium difficulty problem in the Trees category on LeetCode.
This problem requires us to delete a node with a given key in a Binary Search Tree (BST) and return the updated root of the tree.
We'll explore the problem step by step, starting with the problem overview, and then provide an efficient Python solution.
Additionally, we'll discuss the time and space complexity, constraints, and reasoning behind our approach.
Problem Overview
The problem can be broken down into two stages:
1. Search for the node with the given key in the BST.
2. If the node is found, delete it while maintaining the properties of a BST.
To illustrate this, let's consider an example:
Example 1
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: We want to delete the node with the value 3. After deleting, the tree should still be a valid BST.
Please note that there can be multiple valid answers.
For this example, both [5,4,6,2,null,null,7] and [5,2,6,null,4,null,7] are acceptable solutions.
Understanding BST Constraints
Before we delve into the solution, let's briefly review the characteristics of a Binary Search Tree (BST):
– In a BST, for each node:
– All nodes in its left subtree have values less than the node's value.
– All nodes in its right subtree have values greater than the node's value.
This property allows for efficient searching, insertion, and deletion in BSTs.
Delete Node in a BST LeetCode Problem Solution
Now, let's provide an efficient Python solution to solve the Delete Node In A BST problem.
We'll explore two crucial stages: finding the node and then deleting it.
1. Bruteforce Approach
A straightforward way to solve this problem is to perform a depth-first search (DFS) to find the node with the given key and then delete it.
However, this approach can be complex and may require keeping track of the parent node.
2. An Efficient Approach – Recursion
We will use a recursive approach to find and delete the node efficiently while maintaining the BST properties.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return root
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
# Find the minimum value in the right subtree
cur = root.right
while cur.left:
cur = cur.left
root.val = cur.val
root.right = self.deleteNode(root.right, root.val)
return root
This efficient solution utilizes recursion to navigate the BST, find the node, and replace it with a suitable value, preserving the BST's integrity.
Python Code Solution
The Python code solution presented above demonstrates how to implement the algorithm to solve the Delete Node In A BST problem on LeetCode.
Time and Space Complexity
Now, let's analyze the time and space complexity of our solution:
- Time Complexity: The time complexity of this solution is
O(H), where H is the height of the BST.
In a balanced BST, the height is O(log N), where N is the number of nodes.
In the worst case, when the tree is skewed, the height can be O(N).
However, the average time complexity is O(log N) for a balanced BST.
- Space Complexity: The space complexity is
O(H)as well, which accounts for the recursive call stack.
In the worst case, it can be O(N), but on average, it is O(log N) for a balanced BST.
Reasoning Behind Our Approach
The approach presented in this solution is based on the key property of a Binary Search Tree (BST).
We take advantage of the BST's structure to efficiently locate and replace the node with the given key.
The recursive nature of the algorithm simplifies the process, making it both elegant and efficient.
Our approach first searches for the node to delete, and then it employs an intelligent strategy to replace the node, ensuring that the BST's properties are maintained.
The code is easy to follow and can handle a wide range of test cases, making it a reliable solution for the Delete Node In A BST problem.
Related Interview Questions By Company:
- Subarray Sum Equals K LeetCode
- Check If Move Is Legal LeetCode
- Longest Palindromic Subsequence LeetCode
Related Interview Questions By Difficulty:
- Binary Tree Maximum Path Sum LeetCode
- Merge Two Binary Trees LeetCode
- Binary Tree Preorder Traversal LeetCode
Related Interview Questions By Category:
Conclusion
In this blog post, we explored the Delete Node In A BST problem on LeetCode.
We discussed the problem overview, provided an efficient Python solution, analyzed the time and space complexity, and explained the reasoning behind our approach.
This solution leverages the properties of Binary Search Trees to efficiently find and delete nodes, ensuring that the BST's integrity is preserved.
If you found this blog post helpful, please consider leaving a like and subscribing for more coding solutions.
Feel free to comment, ask questions, make suggestions, or share this content to help others.
Question Link: Delete Node in a BST – LeetCode
Thank you for reading, and happy coding!
