LC 700 & LC 98 & LC 235

LeetCode 700 Search in a Binary Search Tree, LeetCode 98 Validate Binary Search Tree, and LeetCode 235 west Common Ancestor of 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 700

Search in a Binary Search Tree (Easy) [link]

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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        
        if root.val > val:
            return self.searchBST(root.left, val)
        if root.val < val:
            return self.searchBST(root.right, val)

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 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 (Medium) [link]

1] Recursive Solution. Inorder traversal the tree, store values in a list, check whether the list is in ascending order. By inorder traversal, the BST should be in the ascending order. Note that BST does not have duplicated values.

# 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:
        candidates = []
        def inorder_traverse(root):
            if not root:
                return
            inorder_traverse(root.left)
            candidates.append(root.val)
            inorder_traverse(root.right)
            
        def is_ordered(lst):
            for i in range(1,len(lst)):
                if lst[i] <= lst[i-1]:
                    return False
            return True

        inorder_traverse(root)
        return is_ordered(candidates)

2] Recursive Solution. Comparing values within the recursion.

# 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:
        max_val = -float('inf')
        def _isValidBST(root):
            nonlocal max_val
            if not root:
                return True

            left = _isValidBST(root.left)
            if root.val > max_val:
                max_val = root.val
            else:
                return False
            right = _isValidBST(root.right)

            return left and right
        return _isValidBST(root)

3] 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 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 235

Lowest Common Ancestor of a Binary Search Tree (Medium) [link]

1] Iterative solution

# 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

2] Recursive solution

# 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':
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root