We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Closest Nodes Queries in a Binary Search Tree

Difficulty: Medium

Problem Description

You are given the root of a binary search tree and an array queries of size n consisting of positive integers. Find a 2D array answer of size n where answer[i] = [min_i, max_i]:

  • min_i is the largest value in the tree that is smaller than or equal to queries[i]. If such a value does not exist, add -1 instead.
  • max_i is the smallest value in the tree that is greater than or equal to queries[i]. If such a value does not exist, add -1 instead.

Return the array answer.

Key Insights

  • The problem leverages the properties of a binary search tree (BST), where the left child is smaller and the right child is larger than the parent node.
  • To efficiently find values less than or equal to and greater than or equal to each query, we can perform binary search operations on the sorted values of the BST.
  • The solution will require an in-order traversal of the BST to retrieve sorted node values before processing the queries.

Space and Time Complexity

Time Complexity: O(n + q * log n) - O(n) for in-order traversal, O(log n) for each query if using binary search. Space Complexity: O(n) - for storing the values from the BST.

Solution

We will first perform an in-order traversal of the BST to obtain the sorted list of node values. Then, for each query, we will use binary search to find the largest value that is less than or equal to the query and the smallest value that is greater than or equal to the query. This approach utilizes a sorted array to efficiently answer each query.

Code Solutions

def closestNodes(root, queries):
    # Helper function for in-order traversal
    def inorder_traversal(node):
        if not node:
            return []
        return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)

    # Store the sorted values of the BST
    sorted_values = inorder_traversal(root)
    answer = []

    for query in queries:
        # Binary search for the closest values
        import bisect
        idx = bisect.bisect_right(sorted_values, query)
        
        # min_i: largest value <= query
        min_i = sorted_values[idx - 1] if idx > 0 else -1
        # max_i: smallest value >= query
        max_i = sorted_values[idx] if idx < len(sorted_values) else -1
        
        answer.append([min_i, max_i])

    return answer
← Back to All Questions