2.4 BSTs

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

Introduction

The section is taken from wiki on BSTs.

Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees.

On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.

Basic Problems

• LC 95 Unique Binary Search Trees II

Variants

* LC 235. Lowest Common Ancestor of a Binary Search Tree

# Find the smallest tree that contains p and q
class Solution(object):

    # Use the fact that BSTs keep their keys in sorted order
    def find_node(self, root, low, high):
        if not root:
            return None
        if low <= root.val and high >= root.val:
            return root
        if low > root.val:
            return self.find_node(root.right, low, high)
        if high < root.val:
            return self.find_node(root.left, low, high)

    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root is None or p is None or q is None:
            return None

        low = min(p.val, q.val)
        high = max(p.val, q.val)

        return self.find_node(root, low, high)