Finding the size of the largest bst subtree contained in a range

Question

This was a recent interview question. The question asked to determine the size of the largest BST subtree contained in the range [x, y]was x < y. BST is defined recursively, where each node has an integer value, the left child of the node, and the right of the child of the node. I was able to get only the total number of nodes in the tree that were within the range, but could not find the largest subtree. Here is the code I used in python:

def solution(x, y, T):
    if T is None:
        return 0
    size = 0
    if x < T.val:
        size += solution(x, y, T.left)
    if x <= T.val and y >= T.val:
        size += 1
    # The following if statement was my attempt at resetting the count
    # whenever we find a node outside the range, but it doesn't work
    if x > T.val or y < T.val:
        size = 0
    if B > T.x:
        size += solution(A, B, T.right)
    return size

The solution should be O(N), where Nis the number of nodes in the tree.

Answer 1

. ( ). [x, y], . ( solution ). , , ).

def min_with_none(a, b):
    """
    Returns the minimum of two elements.   
    If one them is None, the other is returned.
    """
    if a is None:
        return b
    if b is None
        return a
    return min(a, b)


def max_with_none(a, b):
    """
    Returns the maximum of two elements.   
    If one them is None, the other is returned.
    """
    if a is None:
        return b
    if b is None:
        return a
    return max(a, b)


def solution(x, y, T):
    """
    This function returns a tuple 
    (max size of subtree in [x, y] range, total size of the subtree, min of subtree, max of subtree) 
    """
    if T is None:
        return (0, 0, None, None)

    # Solves the problem for the children recursively
    left_ans, left_size, left_min, _ = solution(x, y, T.left)
    right_ans, right_size, _, right_max = solution(x, y, T.right)

    # The size of this subtree
    cur_size = 1 + left_size + right_size

    # The left border of the subtree is T.val or the smallest element in the
    # left subtree (if it not empty)
    cur_min = min_with_none(T.val, left_min)

    # The right border of the subtree is T.val or the largest element in the 
    # right subtree (if it not empty)
    cur_max = max_with_none(T.val, right_max)

    # The answer is the maximum of answer for the left and for the right 
    # subtree
    cur_ans = max(left_ans, right_ans)
    # If the current subtree is within the [x, y] range, it becomes the new answer,
    # as any subtree of this subtree is smaller than itself
    if x <= cur_min and cur_max <= y:
        cur_ans = cur_size 

    return (cur_size, cur_ans, cur_min, cur_max)

, node node.

Answer 2

node BST , [Li,Ri], , node .

:

node i , [Li, Ri], , node, val. i [Li, val − 1]. [val + 1, Ri].

root node [−inf, inf].

Answer 3

, -1 . (sub) , node .

# returns a tuple: (size of T, best valid size among itself and its subtrees)
def f(x,y,T): 
  if T is None: 
    return (0,0)

  l_size, l_best = f(x,y,T.left) 
  r_size, r_best = f(x,y,T.right) 

  if x <= T.value <= y and l_size >= 0 and r_size >= 0:
    return (1 + l_size + r_size,1 + l_size + r_size)
  else:
    return (-1,max(l_best,r_best))