D
DevExCode

LeetCode 270: Closest Binary Search Tree Value Solution

Master LeetCode problem 270 (Closest Binary Search Tree Value), a easy 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:

To find the closest value in a binary search tree (BST) to a given target value, we can perform an in-order traversal of the BST. During the traversal, we keep track of the node whose value is closest to the target value.

  1. Start with the root of the BST.
  2. While traversing the BST:
    • If the current node's value is closer to the target than the previously closest node's value, update the closest node.
    • Move to the left or right child based on the value comparison with the target.
  3. Return the value of the closest node found.

Time Complexity:
The time complexity of this approach is O(logN) on average, where N is the number of nodes in the BST. In the worst case, it can be O(N) for skewed trees.

Space Complexity:
The space complexity is O(1) as we are not using any additional data structures.

:

Solution Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        
        while (root != null) {
            closest = Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
            root = target < root.val ? root.left : root.right;
        }
        
        return closest;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

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

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

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

Can I run code for LeetCode 270 on DevExCode?

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

Back to LeetCode Solutions