D
DevExCode

LeetCode 272: Closest Binary Search Tree Value II Solution

Master LeetCode problem 272 (Closest Binary Search Tree Value II), a hard 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.

Problem Explanation

Explanation:

The problem asks us to find the k closest elements to a given target value target in a binary search tree. To solve this problem, we can perform an in-order traversal of the binary search tree to get a sorted list of values, then find the k closest elements to the target by using a two-pointer approach.

  1. Perform an in-order traversal of the binary search tree to get a sorted list of values.
  2. Initialize two pointers left and right to point to the closest elements to the target.
  3. Iterate through the sorted list of values and update the pointers based on their distances to the target.
  4. Return the sublist of k closest elements.

Time Complexity:

  • The time complexity of this approach is O(n) where n is the number of nodes in the binary search tree.

Space Complexity:

  • The space complexity of this approach is O(n) for storing the sorted list of values.

:

Solution Code

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> values = new ArrayList<>();
        inorderTraversal(root, values);
        
        int left = 0, right = values.size() - 1;
        List<Integer> result = new ArrayList<>();
        
        while (k-- > 0) {
            if (Math.abs(values.get(left) - target) < Math.abs(values.get(right) - target)) {
                result.add(values.get(left++));
            } else {
                result.add(values.get(right--));
            }
        }
        
        return result;
    }
    
    private void inorderTraversal(TreeNode root, List<Integer> values) {
        if (root == null) return;
        
        inorderTraversal(root.left, values);
        values.add(root.val);
        inorderTraversal(root.right, values);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 272 (Closest Binary Search Tree Value II)?

This page provides optimized solutions for LeetCode problem 272 (Closest Binary Search Tree Value II) 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 272 (Closest Binary Search Tree Value II)?

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

Can I run code for LeetCode 272 on DevExCode?

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

Back to LeetCode Solutions