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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Closest Nodes Queries in a Binary Search Tree

Number: 2567

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given the root of a Binary Search Tree (BST) and an array of integer queries, for each query, determine two values: the largest number in the BST that is less than or equal to the query, and the smallest number in the BST that is greater than or equal to the query. If one of these values does not exist in the tree for a particular query, return -1 for that value.

Key Insights

  • Utilize the property of BSTs where an inorder traversal yields a sorted list.
  • Precompute a sorted list of all node values from the BST.
  • For each query, perform binary search on the sorted list to efficiently determine:
    • The greatest value that is less than or equal to the query.
    • The smallest value that is greater than or equal to the query.
  • The binary search allows handling up to 10^5 queries efficiently.

Space and Time Complexity

Time Complexity: O(N + Q log N) where N is the number of nodes in the BST and Q is the number of queries. Space Complexity: O(N) for storing the sorted list of node values.

Solution

The solution involves two main steps. First, perform an inorder traversal of the BST to generate a sorted list of node values. Second, for each query, use binary search to find the correct insertion point in the sorted list. The element just before this insertion point (if it exists) is the largest value less than or equal to the query, and the element at the insertion point (if available) is the smallest value greater than or equal to the query. This leverages the BST’s ordered property and allows for each query to be answered in logarithmic time relative to the number of nodes.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

def closestNodes(root, queries):
    # Helper function to perform inorder traversal and store node values in sorted order
    def inorder(node, arr):
        if not node:
            return
        inorder(node.left, arr)  # Recursively traverse left subtree
        arr.append(node.val)     # Visit current node
        inorder(node.right, arr) # Recursively traverse right subtree

    sorted_vals = []
    inorder(root, sorted_vals)   # Get sorted list from BST
    
    # Import bisect module for binary search operations
    import bisect
    answer = []
    for query in queries:
        # Use bisect_left to find the index where query would fit
        idx = bisect.bisect_left(sorted_vals, query)
        
        # Determine the largest value <= query
        if idx < len(sorted_vals) and sorted_vals[idx] == query:
            min_val = query
        elif idx > 0:
            min_val = sorted_vals[idx - 1]
        else:
            min_val = -1
        
        # Determine the smallest value >= query
        if idx < len(sorted_vals):
            max_val = sorted_vals[idx]
        else:
            max_val = -1

        answer.append([min_val, max_val])
    return answer
← Back to All Questions