Searching - binary search tree

[ahasusie]

search, insert min, max floor, ceiling, rank delete range search

处理BST的问题时大多使用dfs, recursion, divide and conquer, 左右子树分别处理

[ahasusie]

for binary search tree, we can retrieve all the data in sorted order using in-order traversal

class Solution(object):    
    def bstSortedOrder(self, root):
        self.arr = []
        self.inorder(root)
        return self.arr

    def inorder(self, root):
        if not root: return 
        self.inorder(root.left)
        self.arr.append(root.val)
        self.inorder(root.right)

[ahasusie]

270. Closest Binary Search Tree Value
271. Lowest Common Ancestor of a Binary Search Tree
272. Kth Smallest Element in a BST
273. Validate Binary Search Tree
274. Inorder Successor in BST
275. Binary Search Tree Iterator
276. Trim a Binary Search Tree
277. Convert Sorted Array to Binary Search Tree
278. Split BST

Notes: 1/ when dealing with BST problems, we don't care too much about buttom-up/top-down, but use more BST characters, usually handle separately in left/right subtree

[ahasusie]

# 270
class closestValueBSTSolution(object):
    #dfs, recursion, divide and conquer, postorder buttom up
    def closestValueBST1(self, root, target):
        if not root: return None
        if target < root.val:
            if root.left:
                left = self.closestValueBST1(root.left, target)
                if abs(left - target) < abs(root.val - target):
                    return left
        if target > root.val:
            if root.right:
                right = self.closestValueBST1(root.right, target)
                if abs(right - target) < abs(root.val - target):
                    return right
        return root.val

    #dfs, recursion, traversal, preorder top down
    def closestValueBST2(self, root, target):
        self.res = root.val
        self.dfs(root, target)
        return self.res
    def dfs(self, root, target):
        if not root: return None
        if abs(self.res - target) > abs(root.val - target):
            self.res = root.val
        if target < root.val:
            self.dfs(root.left, target)
        else:
            self.dfs(root.right, target)

#find floor of a given number in BST
def floorBST(root, target):
    if not root: return None
    if root.val == target:
        return root
    if root.val > target:
        return floorBST(root.left, target)
    node = floorBST(root.right, target)
    if node:
        return node
    else:
        return root

#find ceil of a given number in BST
def ceilBST(root, target):
    if not root: return -1
    if root.val == target:
        return root.val
    if root.val < target:
        return ceilBST(root.right, target)
    value = ceilBST(root.left, target)
    if value >= target:
        return value
    else:
        return root.val

#search range in BST
def rangeBST(root, lo, hi):
    if not root: return None
    if lo < root.val:
        rangeBST(root.left, lo, hi)
    if lo <= root.val <= hi:
        print root.val
    if root.val < hi:
        rangeBST(root.right, lo, hi)

#230. Kth smallest item in BST
class KthSmallestSolution(object):
    def kthSmallestBST(self, root, k):
        self.res = None
        self.count = k
        self.inorder(root)
        return self.res
    def inorder(self, root):
        if not root: return 
        self.inorder(root.left)
        self.count -= 1
        if self.count == 0:
            self.res = root.val
            return 
        self.inorder(root.right)
#235. Lowest Common Ancestor in BST
#dfs, recursion, divide and conquer
def lcaBST(root, n1, n2):
    if not root: return
    if root.val > max(n1, n2):
        return lcaBST(root.left, n1, n2)
    if root.val < min(n1, n2):
        return lcaBST(root.right, n1, n2)
    if n1 <= root.val <= n2:
        return root