Summary of Binary Search Tree.
LeetCode 700 Search in a Binary Search Tree
# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root is not None:
if root.val < val:
root = root.right
elif root.val > val:
root = root.left
else:
return root
return None
LeetCode 98 Validate Binary Search Tree
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
stack = []
cur = root
pre = None
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre and cur.val <= pre.val:
return False
pre = cur
cur = cur.right
return True
LeetCode 530 Minimum Absolute Difference in BST
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
stack = []
cur = root
pre = None
min_diff = float('inf')
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if pre:
min_diff = min(min_diff, cur.val-pre.val)
pre = cur
cur = cur.right
return min_diff
LeetCode 501 Find Mode in Binary Search Tree
# 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 findMode(self, root: Optional[TreeNode]) -> List[int]:
stack = []
cur = root
pre = None
maxCount = 0
res = []
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
if not pre:
count = 1
elif pre.val == cur.val:
count += 1
else:
count = 1
if count == maxCount: # if multiple modes
res.append(cur.val)
if count > maxCount:
maxCount= count
res.clear()
res.append(cur.val)
pre = cur
cur = cur.right
return res
LeetCode 538 Convert BST to Greater Tree
# 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 __init__(self):
self.pre = TreeNode()
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.traversal(root)
return root
def traversal(self, root):
if not root:
return None
self.traversal(root.right)
root.val += self.pre.val
self.pre = root
self.traversal(root.left)
LeetCode 235 Lowest Common Ancestor of a Binary Search Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
LeetCode 701 Insert into a Binary Search Tree
# 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 insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
pre = None
cur = root
while cur:
if cur.val < val:
pre = cur
cur = cur.right
elif cur.val > val:
pre = cur
cur = cur.left
if pre.val > val:
pre.left = TreeNode(val)
else:
pre.right = TreeNode(val)
return root
LeetCode 450 Delete Node is a BST
# 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
# 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
LeetCode 108 Convert Sorted Array to Binary Search Tree
# 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
root = self.construct(nums, 0, len(nums)-1)
return root
def construct(self, nums, left, right):
if left > right:
return None
mid = left + (right-left)//2
mid_root = TreeNode(nums[mid])
mid_root.left = self.construct(nums, left, mid-1)
mid_root.right = self.construct(nums, mid+1, right)
return mid_root
