Binary Search Tree

Binary Search Tree (BST)

# Property: left.val < node.val < right.val
# Search/Insert/Delete: O(log n) balanced, O(n) skewed

class BST:
    def __init__(self): self.root = None

    def insert(self, val):
        def _ins(node, val):
            if not node: return TreeNode(val)
            if val < node.val: node.left  = _ins(node.left,  val)
            else:              node.right = _ins(node.right, val)
            return node
        self.root = _ins(self.root, val)

    def search(self, val) -> bool:
        node = self.root
        while node:
            if   val == node.val: return True
            elif val <  node.val: node = node.left
            else:                 node = node.right
        return False

    def kth_smallest(self, k) -> int:
        """Inorder traversal -- k-th smallest"""
        stack, node, count = [], self.root, 0
        while stack or node:
            while node: stack.append(node); node = node.left
            node = stack.pop()
            count += 1
            if count == k: return node.val
            node = node.right
        return -1

    def is_valid_bst(self, node, lo=float('-inf'), hi=float('inf')):
        if not node: return True
        if not (lo < node.val < hi): return False
        return (self.is_valid_bst(node.left, lo, node.val) and
                self.is_valid_bst(node.right, node.val, hi))