LeetCode 501 Find Mode in Binary Search Tree, LeetCode 530 Minimum Absolute Difference in BST, and LeetCode 701 Insert into a Binary Search Tree. [Using two pointers: pre and cur]
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 501
Find Mode in Binary Search Tree (Easy) [link]
Because it’s a binary search tree, same numbers are next to each other.
# 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 530
Minimum Absolute Difference in BST. (Easy) [link]
Inorder traversal the tree, store values in a list, the list is in ascending order. This question is asking to find min difference in a sorted list.
Remember how to record two pointers in recursion!
1] Recursive Solution.
# 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:
candidates = []
def getCandidates(root):
if not root:
return
getCandidates(root.left)
candidates.append(root.val)
getCandidates(root.right)
def findMinimum(lst):
min_diff = float('inf')
for i in range(1,len(lst)):
min_diff = min(min_diff, lst[i]-lst[i-1])
return min_diff
getCandidates(root)
return findMinimum(candidates)
2] Iterative Solution.
# 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 701
Insert into a Binary Search Tree (Medium) [link]
1] Recursive Solution. We return root.left or root.right because we want the updated 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)
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
if root.val < val:
root.right = self.insertIntoBST(root.right, val)
return root
2] Iterative Solution.
# 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
