Do you think IIT Guwahati certified course can help you in your career?
Introduction
The tree data structure is used to display data in a hierarchical style. A tree can be defined as a group of nodes (items or entities) connected by links to make a hierarchy.
In this article, we will briefly discuss binary search tree data structure, examples, approach, and how to find the Closest element to a target value in Binary Search Tree, time, and space complexity.
Binary Search tree
A binary search tree is a data structure that allows us to quickly retain a sorted list of numbers. A binary tree is one in which each tree node can only have two child nodes.
Problem statement
We are given a binary Search tree and a target value K and have to find the node with a minimum absolute difference from the given target value K.
Sample Example 1
Input
For the above tree, we have the target value of 11.
12
Sample Example 2
Input
For the above tree, we have the target value of 10.
12
In the above example, we are just trying to find out the closest element to a target value in Binary Search Treeby the approach given below.
Approach
🔺A simple approach to this problem is to record the Inorder traversal of a given binary search tree in an auxiliary array.
🔺Then identify the node with the smallest absolute difference with a given target value K in linear time by taking the absolute difference of each element.
🔺A better approach to this problem is to take advantage of the characteristics of BST. below is the algorithm to solve the problem:
If the target value K is present in the provided BST, the node with the smallest absolute difference is selected.
If the desired value K is smaller than the value of the current node, shift to the left child.
If the desired value K is greater than the value of the current node, shift to the right child.
Algorithm
🔻 To solve this problem, we have created a function to find the minimum difference between nodes.
🔻The minimum difference function has two arguments one is the node pointer, and another is the target value.
🔻 We are finding the minimum difference by the following method:
🔻 Finally, we will print the closest element to a target value in Binary Search Tree.
Java code
// Java program to find the Closest element to a target value in Binary Search Tree.
import java.util.*;
import java.io.*;
class Solution {
static int mindifference, mindifferencekey;
static class Node {
int key;
Node left, right;
};
static Node newnode(int key) {
Node node = new Node();
node.key = key;
node.left = node.right = null;
return (node);
}
// finding a node with minimum difference with given K
// to find Closest element to a target value in Binary Search Tree
static void maxDifference(Node pointer, int k) {
if (pointer == null)
return;
if (pointer.key == k) {
mindifferencekey = k;
return;
}
if (mindifference > Math.abs(pointer.key - k)) {
mindifference = Math.abs(pointer.key - k);
mindifferencekey = pointer.key;
}
if (k < pointer.key)
maxDifference(pointer.left, k);
else
maxDifference(pointer.right, k);
}
// Driver program to find Closest element to a target value in Binary Search
// Tree
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("enter the root element");
Node root = newnode(sc.nextInt());
System.out.println("enter the root left element");
root.left = newnode(sc.nextInt());
System.out.println("enter the root right element");
root.right = newnode(sc.nextInt());
System.out.println("enter the root left left element");
root.left.left = newnode(sc.nextInt());
System.out.println("enter the root left right element");
root.left.right = newnode(sc.nextInt());
System.out.println("enter the root left right left element");
root.left.right.left = newnode(sc.nextInt());
System.out.println("enter the root left right right element");
root.left.right.right = newnode(sc.nextInt());
System.out.println("enter the root right right element");
root.right.right = newnode(sc.nextInt());
System.out.println("enter the root right right left element");
root.right.right.left = newnode(sc.nextInt());
int k = 18;
// Initialize minimum difference
mindifference = 999999999;
mindifferencekey = -1;
maxDifference(root, k);
// finding the Closest element to a target value in Binary Search Tree
System.out.println("The minimum difference key is: " + mindifferencekey);
}
}
You can also try this code with Online Java Compiler
Time complexity: O(h), since h is the height of the binary search tree.
Space complexity: O(N), since we are taking the data from the user for each node. Check out this problem - Largest BST In Binary Tree
Frequently Asked Questions
What is the purpose of a tree data structure?
The main purpose of tree data structure is to store hierarchical data, such as folder structure, organization structure, and XML/HTML. A binary Search Tree is a tree that allows you to quickly search, insert, and delete data that has been sorted. It also helps you to find the object that is nearest to you. Heap is a tree data structure that uses arrays to construct priority queues.
How can you say that BST is valid?
A BST is valid if and only if all nodes in the left subtree have values smaller than the node's value. The values of all nodes in the right subtree should be greater than the root node value, whereas the values of all nodes in the left subtree should be smaller than the root node.
Describe a self-balanced tree.
Self-balanced binary search trees retain their height as minimal as possible when insertion and deletion operations are performed. To be self-balanced, a BST must constantly obey the BST rules, with the left subtree having lower-valued values and the right subtree having high-valued keys. The use of two operations accomplishes this:
right rotation
left rotation
Conclusion
In this article, we have discussed the binary search tree data structure in brief, examples, approach, and how to find the closest element to a target value in Binary Search Tree, time, and space complexity with O(h) time complexity, and O(N) space complexity.
569+ registered 
