Solution to LeetCode 450 Delete Node is a BST, and LeetCode 669 Trim a Binary Search Tree.
A binary search tree is a tree that satisfies these constraints:
1 The left subtree of a node contains only nodes with keys less than the node’s key.
2 The right subtree of a node contains only nodes with keys greater than the node’s key.
3 Both the left and right subtrees must also be binary search trees.
LeetCode 450
Delete Node is a BST. (Medium) [link]
There are two steps: 1 find the node 2 delete the node. Deleting nodes from a BST is complicated because we might need to change the structure.
1] if no such node, return root.
2] if such node is found.
a] if left child and right child of the node are both None, delete the node directly.
b] if the left child of the node is None, while the right child of the node is not None, replace the node with its right child
c] if the right child of the node is None, while the left child of the node is not None, replace the node with its left child.
d] if the right child and the left child of the node are both None, delete the node, move the left child of the node to the most left leaf of the right child of the node.
# Definition for a binary tree node.
# 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 None
if root.val < key:
root.right = self.deleteNode(root.right, key)
elif root.val > key:
root.left = self.deleteNode(root.left, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
#if all non None
node = root.right
while node.left:
node = node.left
node.left = root.left
root = root.right
return root
LeetCode 669
Trim a Binary Search Tree (Medium) [link]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root:
return None
if root.val > high:
return self.trimBST(root.left, low ,high)
if root.val < low:
return self.trimBST(root.right, low ,high)
if low <= root.val <= high:
root.left = self.trimBST(root.left, low ,high)
root.right = self.trimBST(root.right, low ,high)
return root
