🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we'll solve a common problem in binary search trees (BSTs) - finding the value in the BST that is closest to a given target value. This problem is a great exercise in understanding the properties of BSTs and how to efficiently traverse them.
Problem
Given a non-empty binary search tree and a target value, the task is to find the value in the BST that is closest to the target.
2. Solution Steps
1. Start by initializing a variable to keep track of the closest value found so far.
2. Traverse the BST starting from the root. At each node, update the closest value if the current node's value is closer to the target than the previously recorded closest value.
3. Depending on the target value and the current node's value, move to the left or right child of the current node.
4. Continue this process until all nodes have been examined.
5. Return the closest value found.
3. Code Program
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
// Main method for testing
public static void main(String[] args) {
TreeNode root = new TreeNode(9);
root.left = new TreeNode(4);
root.right = new TreeNode(17);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(6);
root.left.right.left = new TreeNode(5);
root.left.right.right = new TreeNode(7);
root.right.right = new TreeNode(22);
root.right.right.left = new TreeNode(20);
int target = 12;
System.out.println("Closest value to " + target + " is: " + closestValue(root, target));
}
// Method to find the value in the BST that is closest to the target
public static int closestValue(TreeNode root, int target) {
int closest = root.val; // Initialize closest value
TreeNode current = root;
while (current != null) {
// Update closest value if the current value is closer to the target
if (Math.abs(target - current.val) < Math.abs(target - closest)) {
closest = current.val;
}
// Move to the left or right child
if (target < current.val) {
current = current.left;
} else {
current = current.right;
}
}
return closest; // Return the closest value found
}
}
Output:
Closest value to 12 is: 9
Explanation:
In the given BST, the value that is closest to the target value 12 is 9.
The closestValue method traverses the tree, starting from the root. At each step, it checks if the current node's value is closer to the target than the previously recorded closest value. It then moves left or right depending on how the current node's value compares to the target, leading to an efficient search for the closest value.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment