D
DevExCode

LeetCode 2476: Closest Nodes Queries in a Binary Search Tree Solution

Master LeetCode problem 2476 (Closest Nodes Queries in a Binary Search Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2476. Closest Nodes Queries in a Binary Search Tree

Medium
ArrayBinary SearchTreeDepth-First SearchBinary Search TreeBinary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a modified in-order traversal of the binary search tree. At each node, we compare the node's value with the query value to update the closest smaller and closest larger values found so far. We update these values as we traverse down the tree, ensuring that we maintain the closest values to the query.

Algorithm:

  1. Initialize two variables closestSmaller and closestLarger to store the closest smaller and larger values found so far.
  2. Traverse the binary search tree in an in-order manner.
  3. At each node:
    • If the node's value is smaller than or equal to the query value, update closestSmaller if needed.
    • If the node's value is larger than or equal to the query value, update closestLarger if needed.
  4. Continue the traversal until reaching the end of the tree.
  5. Return the final closest smaller and closest larger values for each query.

Time Complexity:

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary search tree.

Space Complexity:

The space complexity is O(1) as we are using only a constant amount of extra space for storing closest smaller and closest larger values.

:

Solution Code

class Solution {
    public int[][] closestNodesQueries(TreeNode root, int[] queries) {
        int[][] answer = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            int closestSmaller = -1;
            int closestLarger = -1;
            TreeNode curr = root;
            while (curr != null) {
                if (curr.val <= queries[i]) {
                    closestSmaller = curr.val;
                    curr = curr.right;
                } else {
                    closestLarger = curr.val;
                    curr = curr.left;
                }
            }
            answer[i][0] = closestSmaller;
            answer[i][1] = closestLarger;
        }
        return answer;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 2476 (Closest Nodes Queries in a Binary Search Tree)?

This page provides optimized solutions for LeetCode problem 2476 (Closest Nodes Queries in a Binary Search Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2476 (Closest Nodes Queries in a Binary Search Tree)?

The time complexity for LeetCode 2476 (Closest Nodes Queries in a Binary Search Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2476 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2476 in Java, C++, or Python.

Back to LeetCode Solutions