Search Range in Binary Search Tree

Problem

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.

Have you met this question in a real interview? Yes Example If k1 = 10 and k2 = 22, then your function should return [12, 20, 22].

    20
   /  \
  8   22
 / \
4   12

思路

因为是binary search tree,所以从小到大的traversal就应该是inorder 用inorder的模板

Solution

class Solution:
    """
    @param root: The root of the binary search tree.
    @param k1 and k2: range k1 to k2.
    @return: Return all keys that k1<=key<=k2 in ascending order.
    """     
    def searchRange(self, root, k1, k2):
        # write your code here
        if not root:
            return []
        list = []                                                                                                                         
        if root.left:
            list.extend(self.searchRange(root.left, k1, k2))
        if root.val >= k1 and root.val <= k2:
            list.append(root.val)
        if root.right:
            list.extend(self.searchRange(root.right, k1, k2))
        return list