How do you solve Closest Nodes Queries in a Binary Search Tree on LeetCode?

Closest Nodes Queries in a Binary Search Tree (LeetCode #2476) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) for sorting + O(m log n) for m queries time complexity and O(n) space complexity. Key insight: Binary Search Trees are inherently sorted, allowing efficient search operations.

What is the time complexity of Closest Nodes Queries in a Binary Search Tree?

The optimal solution for Closest Nodes Queries in a Binary Search Tree runs in O(n log n) for sorting + O(m log n) for m queries time and uses O(n) space. The in-order traversal takes O(n) time to create a sorted list, and each query is resolved in O(log n) time due to binary search.

What is the brute force solution for Closest Nodes Queries in a Binary Search Tree?

The brute force approach for Closest Nodes Queries in a Binary Search Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we will traverse the entire binary search tree for each query to find the required values. This is straightforward but inefficient, as it checks every node for each query. The optimal Optimal Solution approach improves this to O(n log n) for sorting + O(m log n) for m queries.

What are the interview tips for Closest Nodes Queries in a Binary Search Tree?

Always clarify the problem constraints and expected output format. Consider edge cases, such as queries that are less than the smallest or greater than the largest values in the tree. Practice writing both brute force and optimal solutions to understand the trade-offs.

What are common mistakes when solving Closest Nodes Queries in a Binary Search Tree?

Not performing in-order traversal correctly to maintain sorted order. Confusing min and max conditions when searching.

#2476

Closest Nodes Queries in a Binary Search Tree

Medium

ArrayBinary SearchTreeDepth-First SearchBinary Search TreeBinary TreeBinary SearchIn-order TraversalArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n) for sorting + O(m log n) for m queries
Space	O(1)	O(n)

💡

Intuition

Time O(n log n) for sorting + O(m log n) for m queriesSpace O(n)

By converting the BST into a sorted array, we can efficiently find the closest nodes using binary search, which allows us to answer each query in logarithmic time.

⚙️

Algorithm

3 steps

1Step 1: Perform an in-order traversal of the BST to create a sorted array of its values.
2Step 2: For each query, use binary search to find the largest value less than or equal to the query and the smallest value greater than or equal to the query.
3Step 3: Store the results in the answer array.

solution.py23 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def closestNodes(root, queries):
9    sorted_vals = []
10    def in_order(node):
11        if not node:
12            return
13        in_order(node.left)
14        sorted_vals.append(node.val)
15        in_order(node.right)
16    in_order(root)
17    from bisect import bisect_left, bisect_right
18    result = []
19    for q in queries:
20        min_val = sorted_vals[bisect_right(sorted_vals, q) - 1] if bisect_right(sorted_vals, q) > 0 else -1
21        max_val = sorted_vals[bisect_left(sorted_vals, q)] if bisect_left(sorted_vals, q) < len(sorted_vals) else -1
22        result.append([min_val, max_val])
23    return result

ℹ

Complexity note: The in-order traversal takes O(n) time to create a sorted list, and each query is resolved in O(log n) time due to binary search.

1Binary Search Trees are inherently sorted, allowing efficient search operations.
2Using binary search on a sorted array optimizes query responses.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.