2476. Closest Nodes Queries in a Binary Search Tree

MediumTreeDepth-First SearchArrayBinary SearchBinary Tree
Leetcode Link

Problem Description

The given problem presents us with a binary search tree (BST) and a series of queries. Our task is to respond to each query with a pair of values based on the contents of the BST. Specifically, for each query, we need to find two values from the tree:

  1. min_i: The largest value in the tree that is less than or equal to the query value. If there's no such value, we should return -1.
  2. max_i: The smallest value in the tree that is greater than or equal to the query value. If there's no such value, we should return -1.

The objective is to create a 2D array (a list of lists in Python) named answer, where each element answer[i] is a [min_i, max_i] pair, corresponding to each query. The problem measures our understanding of BST navigation and the search for boundary conditions relative to arbitrary target values.

Flowchart Walkthrough

Let's examine the use of an algorithm using the Flowchart. Here's a step-by-step analysis to determine the appropriate algorithm for leetcode 2476. Closest Nodes Queries in a Binary Search Tree:

Is it a graph?

  • Yes: A binary search tree is a specialized form of a graph, with nodes connected in a parent-child relationship.

Is it a tree?

  • Yes: By definition, a Binary Search Tree (BST) is a tree.

DFS

  • As determined by the flowchart, since we're dealing with a tree and no further specifications lead us beyond this decision in the chart, Depth-First Search (DFS) is the appropriate algorithm to use in this scenario.

Conclusion:

  • The flowchart leads us directly to utilizing Depth-First Search (DFS) when we confirm that the problem is set within a tree structure, as is the case with binary search trees in leetcode 2476. DFS is ideally suited for problems involving tree structures because it can explore all nodes and edges from root to leaves deeply, which is key for various tree-related queries.

Intuition

In order to solve this challenge, we can leverage the properties of a binary search tree. A BST is organized in such a way that for any node with a value v, any descendant node in its left subtree will have a value less than v, and any descendant node in its right subtree will have a value greater than v. This allows us to perform efficient tree traversals to find the min_i and max_i values for each query.

The provided solution takes the following steps:

  1. Perform an in-order traversal of the BST and collect all the node values in a list called nums. In a BST, an in-order traversal guarantees that the values will be sorted in ascending order. This step is important because it then allows us to use binary search techniques to quickly locate the correct min_i and max_i values for each query.

  2. Iterate through each value in the queries list. For each query value v, we perform two binary search operations to find the closest values in the sorted list nums that satisfy our conditions:

    • To find min_i, we search for the insertion point of v as if we would insert it, then we take one step back (if we are not at the beginning of the list), as this would give us the largest value smaller than or equal to v.

    • To find max_i, we search for the insertion point directly, which gives us the smallest value greater than or equal to v.

  3. We check the index bounds to make sure we're adding legitimate values from our list or -1 if the index is out of range (indicating that no such value exists in the BST for our query).

Using efficient binary search operations (bisect_left and bisect_right from the bisect module in Python), the provided solution minimizes the search time to locate min_i and max_i, thereby optimizing the overall time complexity of the problem.

Learn more about Tree, Depth-First Search, Binary Search and Binary Tree patterns.

Solution Approach

The implementation of the solution follows a straightforward approach that breaks the problem into manageable steps as follows:

  1. In-Order Traversal: Since we need to find the nearest values around each query from a binary search tree, we first collect these values in an organized manner. By performing an in-order traversal of the BST, we traverse left subtree, then the root, and finally the right subtree. The traversal yields a sorted array nums of all values in the BST in ascending order, where each element corresponds to the value of each node visited.

  2. Binary Search: With the sorted list of BST values, we then utilize binary search to quickly find the min_i and max_i for each query value v. Python’s bisect module provides two handy functions to assist with this:

    • bisect_right(nums, v) returns the insertion point for v in the list nums. If v is already in nums, the insertion point will be to the right of any existing entries. We subtract 1 to find the largest value that is less than or equal to v.

    • bisect_left(nums, v) returns the insertion point for v in the list nums. If v is already in nums, the insertion point will be the index of the leftmost v.

  3. Index Checking and Result Collection: After finding the insertion points using binary search, we must ensure these indices are valid (i.e., within the range of the list). If they're valid, we retrieve the corresponding values as our min_i and max_i. If an index is out of bounds, it implies no such value exists in the BST, and we add -1 for that particular bound (either min_i or max_i). We append these pairs [min_i, max_i] to our answer for each query.

  4. Final Output: After iterating through all queries, our answer list contains the pairs for each query in accordance to the rules provided by the problem statement.

The data structures used in this approach are:

  • A list nums to hold the in-order traversal of the BST values.
  • A list ans or answer that accumulates the pairs [min_i, max_i] for each query.

The algorithms and patterns used are:

  • In-Order Traversal: This recursive pattern is used to traverse and collect values from the BST in sorted order.
  • Binary Search: This algorithm is used (with the help of the bisect module) to efficiently find the indices that will help derive min_i and max_i for each query.

This approach leverages the efficiencies of binary search trees and binary search algorithms to minimize the time complexity of searching for nearest values for a series of queries.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we have the following BST and a query list [7, 15, 3]:

        10
       /  \
      5    15
     / \     \
    3   7     17

To answer the queries according to the provided solution approach, we'll follow these steps:

  1. Perform in-order traversal of the BST:

    First, we visit the leftmost node (3), then its parent (5), its right sibling (7), and so on, until we've visited all nodes. This will give us nums = [3, 5, 7, 10, 15, 17].

  2. For each query value v, find min_i and max_i using binary search. Let's start with the first query 7:

    • Using binary search to find min_i: We find the insertion point of 7. Since 7 is in the list, the insertion point is to its right. We step back one index and find that min_i is itself 7.

    • Using binary search to find max_i: We find the insertion point for 7. Since 7 is in the list, max_i is also 7.

    Thus, the answer to the first query is [7, 7].

  3. Repeat for the second query, 15:

    • min_i search: The insertion point for 15 would be its own position, so stepping one index back gives us 10. However, since 15 is in the list, min_i is 15.

    • max_i search: The insertion point for 15 is its own index, so max_i is 15.

    Therefore, the answer to the second query is [15, 15].

  4. Finally, for the third query, 3:

    • min_i search: Since 3 is the first element in our list, we cannot step back, which means there is no smaller value. Hence, min_i is 3.

    • max_i search: The insertion point for 3 is at its own position, so max_i is 3.

    Hence, the answer to the third query is [3, 3].

  5. Compile the final answer after evaluating all queries:

    The answer array accumulates the result for each query consecutively. As such, we get answer = [[7, 7], [15, 15], [3, 3]].

Following the described solution approach, using the in-order traversal list, nums, and binary search operations for both min_i and max_i, we were able to derive the closest values from the BST for each query efficiently.

Solution Implementation

1from bisect import bisect_left, bisect_right
2from typing import List, Optional
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def closest_nodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
13        # Helper function to perform in-order traversal of the binary tree
14        # and collect the node values in a sorted list.
15        def inorder_traversal(node):
16            if node is None:
17                return
18            inorder_traversal(node.left)  # Traverse left subtree
19            sorted_values.append(node.val)  # Visit/Process the node
20            inorder_traversal(node.right)  # Traverse right subtree
21
22        # Start in-order traversal and initialize the list to hold sorted node values
23        sorted_values = []
24        inorder_traversal(root)
25
26        # Initialize the list to hold the answer for each query
27        answer = []
28
29        # Process each query to find the closest nodes
30        for value in queries:
31            # Use binary search to find the insert position for the query value
32            right_index = bisect_left(sorted_values, value)
33            left_index = right_index - 1
34          
35            # Get the closest value on the left, if available
36            left_val = sorted_values[left_index] if 0 <= left_index < len(sorted_values) else -1
37          
38            # Get the closest value on the right, if available          
39            right_val = sorted_values[right_index] if 0 <= right_index < len(sorted_values) else -1
40          
41            # Append the closest values found to the answer list
42            answer.append([left_val, right_val])
43
44        # Return the list of answers for all queries
45        return answer
46
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5// Definition for a binary tree node.
6class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10  
11    TreeNode() {}
12  
13    TreeNode(int val) { 
14        this.val = val; 
15    }
16  
17    TreeNode(int val, TreeNode left, TreeNode right) {
18        this.val = val;
19        this.left = left;
20        this.right = right;
21    }
22}
23
24class Solution {
25    // Store the sorted values of the tree
26    private List<Integer> sortedValues = new ArrayList<>();
27
28    /**
29     * Returns the closest node values from the tree for each query.
30     *
31     * @param root The root node of the binary tree.
32     * @param queries A list of integer queries.
33     * @return A list of lists, where each list contains two values (previous and next closest).
34     */
35    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
36        // Perform an in-order traversal to get the sorted values of the binary search tree.
37        inOrderTraversal(root);
38      
39        // Prepare the list to hold the answer.
40        List<List<Integer>> answer = new ArrayList<>();
41      
42        // Iterate over each query to find closest values.
43        for (int queryValue : queries) {
44            // The predecessor index (closest smaller or equal value).
45            int predecessorIndex = binarySearch(queryValue + 1) - 1;
46            // The successor index (closest larger value).
47            int successorIndex = binarySearch(queryValue);
48            // The predecessor value, or -1 if there isn't one.
49            Integer predecessor = predecessorIndex >= 0 && predecessorIndex < sortedValues.size() ? sortedValues.get(predecessorIndex) : -1;
50            // The successor value, or -1 if there isn't one.
51            Integer successor = successorIndex >= 0 && successorIndex < sortedValues.size() ? sortedValues.get(successorIndex) : -1;
52            // Add the pair (predecessor, successor) to the answer.
53            answer.add(Arrays.asList(predecessor, successor));
54        }
55        return answer;
56    }
57
58    /**
59     * Performs a binary search to find the index of the smallest value greater than or equal to x.
60     *
61     * @param target The target value to search for.
62     * @return The index of the target value or the index where it should be placed.
63     */
64    private int binarySearch(int target) {
65        int left = 0, right = sortedValues.size();
66        while (left < right) {
67            int mid = (left + right) >> 1; // Equivalent to dividing by 2.
68            if (sortedValues.get(mid) >= target) {
69                right = mid;
70            } else {
71                left = mid + 1;
72            }
73        }
74        return left;
75    }
76
77    /**
78     * Performs an in-order traversal of the tree storing the elements in a sorted list.
79     *
80     * @param node The current node of the tree.
81     */
82    private void inOrderTraversal(TreeNode node) {
83        if (node == null) {
84            return;
85        }
86        // First, visit the left subtree.
87        inOrderTraversal(node.left);
88        // Then, visit the current node.
89        sortedValues.add(node.val);
90        // Finally, visit the right subtree.
91        inOrderTraversal(node.right);
92    }
93}
94
1// Definition for a binary tree node.
2struct TreeNode {
3    int val;
4    TreeNode *left;
5    TreeNode *right;
6    // Constructor for creating a new node with no children.
7    TreeNode() : val(0), left(nullptr), right(nullptr) {}
8    // Constructor for creating a new node with a given value with no children.
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    // Constructor for creating a new node with a value and specified left and right children.
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
17        // This vector will store the in-order traversal of the tree, which
18        // gives us the elements in ascending order.
19        vector<int> inorderTraversal;
20        // Recursive lambda function to perform in-order DFS traversal.
21        function<void(TreeNode*)> dfs = [&](TreeNode* node) {
22            if (!node) return;
23            dfs(node->left);
24            inorderTraversal.emplace_back(node->val);
25            dfs(node->right);
26        };
27        // Perform the in-order traversal starting from the root.
28        dfs(root);
29
30        // This vector will hold the final results.
31        vector<vector<int>> results;
32        int n = inorderTraversal.size();
33        // Go through each query to find the closest nodes
34        for (int& value : queries) {
35            // Find the first number that is greater than the query value.
36            int upperIndex = upper_bound(inorderTraversal.begin(), inorderTraversal.end(), value) - inorderTraversal.begin() - 1;
37            // Find the first number that is not less than the query value.
38            int lowerIndex = lower_bound(inorderTraversal.begin(), inorderTraversal.end(), value) - inorderTraversal.begin();
39
40            // Check if the 'upperIndex' is within the bounds of 'inorderTraversal'.
41            int closerLowerValue = upperIndex >= 0 && upperIndex < n ? inorderTraversal[upperIndex] : -1;
42            // Check if the 'lowerIndex' is within the bounds of 'inorderTraversal'.
43            int closerUpperValue = lowerIndex >= 0 && lowerIndex < n ? inorderTraversal[lowerIndex] : -1;
44
45            // Store the result for the current query.
46            results.push_back({closerLowerValue, closerUpperValue});
47        }
48        // Return the list of closest node values for each query.
49        return results;
50    }
51};
52
1// TypeScript types for the TreeNode structure and the Solution's methods.
2
3// Binary tree node structure definition.
4interface TreeNode {
5  val: number;
6  left: TreeNode | null;
7  right: TreeNode | null;
8}
9
10// Function to perform an in-order traversal of a binary tree
11// starting from the given root.
12function inorderTraversal(root: TreeNode | null): number[] {
13  const result: number[] = [];
14  const traverse = (node: TreeNode | null) => {
15    if (node === null) return;
16    traverse(node.left);
17    result.push(node.val);
18    traverse(node.right);
19  };
20  traverse(root);
21  return result;
22}
23
24// Function to find the closest nodes for each query from the given binary tree.
25function closestNodes(root: TreeNode | null, queries: number[]): number[][] {
26  // Perform the in-order traversal to get elements in sorted (ascending) order.
27  const traversalResult: number[] = inorderTraversal(root);
28
29  // This array will hold the final results.
30  const results: number[][] = [];
31  const length: number = traversalResult.length;
32
33  // For each query, find the closest nodes.
34  queries.forEach((value) => {
35    // Find the index of the first number greater than the query value.
36    const upperIndex = binarySearchUpper(traversalResult, value);
37    // Find the index of the first number not less than the query value.
38    const lowerIndex = binarySearchLower(traversalResult, value);
39
40    // Compute the values closest to the query.
41    const closerLowerValue = upperIndex > 0 && upperIndex < length ? traversalResult[upperIndex - 1] : -1;
42    const closerUpperValue = lowerIndex >= 0 && lowerIndex < length ? traversalResult[lowerIndex] : -1;
43
44    // Store the result for the current query.
45    results.push([closerLowerValue, closerUpperValue]);
46  });
47
48  // Return the list of closest node values for each query.
49  return results;
50}
51
52// Helper function for binary search to find the upper bound index.
53function binarySearchUpper(arr: number[], target: number): number {
54  let low = 0;
55  let high = arr.length;
56  while (low < high) {
57    let mid = Math.floor((low + high) / 2);
58    if (arr[mid] > target) {
59      high = mid;
60    } else {
61      low = mid + 1;
62    }
63  }
64  return low;
65}
66
67// Helper function for binary search to find the lower bound index.
68function binarySearchLower(arr: number[], target: number): number {
69  let low = 0;
70  let high = arr.length;
71  while (low < high) {
72    let mid = Math.floor((low + high) / 2);
73    if (arr[mid] < target) {
74      low = mid + 1;
75    } else {
76      high = mid;
77    }
78  }
79  return low;
80}
81

Time and Space Complexity

Time Complexity

The time complexity of the function is determined by several components:

  1. Depth-First Search (DFS) for In-Order Traversal: The function dfs performs an in-order traversal of the binary tree to get a sorted list of all node values in nums. This step visits each node exactly once. Therefore, if the tree has n nodes, the complexity is O(n).

  2. Binary Search for Each Query: For each query value in queries, the bisect_right and bisect_left functions from the bisect module are used to find the closest nodes. Both functions perform a binary search on the sorted list nums, which has a time complexity of O(log n) per search.

Given that there are q queries, the total time complexity for all binary searches combined is O(q log n).

Combining these two parts, the overall time complexity is O(n + q log n).

Space Complexity

The space complexity of the function also consists of multiple parts:

  1. Space for Storing Node Values (nums): The in-order traversal stores all node values in the list nums, so it uses O(n) space.

  2. Recursive Stack Space: In the worst case (a completely unbalanced tree), the dfs recursion can go up to n deep, leading to a space complexity of O(n).

  3. Space for Answer List (ans): The list ans that stores the results for each query is sized according to the number of queries, which is q. Thus, it contributes an additional O(q) space.

The combined space complexity is dominated by the larger of O(n) and O(q), which is O(n + q) because we have to store each separately.

In summary:

  • Time Complexity: O(n + q log n)
  • Space Complexity: O(n + q)

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Want a Structured Path to Master System Design Too? Don’t Miss This!