Closest Binary Search Tree Value in Java
Given a target node K and a binary search tree, the task is to find the node with the least absolute difference for the specified target value K.
Example 1:
Input:
int k = 4
Output:
The closest element in the binary search tree is 3
Explanation:
For the given value, the nearest values are 3 and 6. Now, calculate the difference between 3 and 6, i.e. (4 - 3 = 1 and 6 - 4 = 2), as the least difference is with 3. Hence, the closest element is 3.
Example 2:
Input:
int k = 7
Output:
The closest element in the binary search tree is 6
Explanation:
For the given value, the nearest values are 6 and 8. Now, calculate the difference between 6 and 8, i.e. (7 - 6 = 1 and 8 - 7 = 1). As the obtained difference is equal, check with numbers performed subtraction and select the least number. Hence, 6 is the least number; thus, the output is 6.
Approach: Morris traversal
Morris traversal is a space-efficient method that eliminates the necessity for recursion or stack/queue in constant space O(1) while performing in-order tree traversals. Morris' traversal is dependent on Threaded Binary trees, which rely on a tree's NULL pointers to point to either predecessor or successor nodes. Memory gets wasted by n+1 NULL pointers, just like in a binary tree with n nodes.
The algorithm described below consists of a simple in-order tree traversal using Morris Traversal. During this process, we compare the data of each node to the key and look for differences. We also keep track of two variables, "diff" and "closest," which are changed whenever a node gets closer to the key. After completing the in-order tree traversal, we have the closest node.
Algorithm:
Step 1: Initialize Current as the root.
Step 2: Initialize the value of a variable called diff to INT_MAX.
Step 3: Initialize the value of the nearest variable, which will be a pointer to the node and be returned.
Step 4: If current value = = “NULL”
Step 4.1: If there are no children present on the left side.
Step 4.1.1: Determine diff as the absolute difference between the current node and the key if the absolute difference between the key and the current data is less than diff. Select the closest as an active node. If not, go to the current child on the right.
Step 5: If else, continue following steps.
Step 5.1: Find the current node's inorder predecessor. The left child or the rightmost node in the left subtree is the in-order predecessor.
Step 5.2: If the inorder predecessor's right child is NULL, create threads between nodes by setting current as the correct child of its in-order predecessor. Then, transfer the active node to its left child.
Step 6: If the threaded link between the current node and its in-order predecessor already exists.
Step 6.1: Set the in-order predecessor node's right value to NULL.
Step 6.2: If the key's absolute difference from the data as of right now is less than diff:
Step 6.2.1: Declare the diff variable to be the absolute difference between the key and the current node.
Step 6.2.2: Assign the current node to the closest one.
Step 6.3: Shift the current to the appropriate child.
Step 7: After traversing the entire tree, we have already reached the closest node, so we just need to return the closest value.
Implementation:
FileName: MorrisTraversal.java
import java.io.*;
import java.util.*;
public class MorrisTraversal
{
static class Node
{
int data;
Node leftNode, rightNode;
};
// creation of a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.leftNode = temp.rightNode = null;
return temp;
}
// Function that uses Morris Traversal to identify the Node that is closest to the given key in BST
static Node closestNode(Node root, int key)
{
int difference = Integer.MAX_VALUE;
Node currNode = root;
Node closestNode = null;
while (currNode != null)
{
if (currNode.leftNode == null)
{
//If the current difference is less than the previous difference, update the difference.
if (difference > Math.abs(currNode.data - key))
{
difference = Math.abs(currNode.data - key);
closestNode = currNode;
}
currNode = currNode.rightNode;
}
else
{
// finding the inorder predecessor
Node pre = currNode.leftNode;
while (pre.rightNode != null && pre.rightNode != currNode)
pre = pre.rightNode;
if (pre.rightNode == null)
{
pre.rightNode = currNode;
currNode = currNode.leftNode;
}
// interconnected link between currNode and
// the existence of its predecessor
else
{
pre.rightNode = null;
//Update the diff and set it closest to the current
// if a closer Node is found.
if (difference > Math.abs(currNode.data - key))
{
difference = Math.abs(currNode.data - key);
closestNode = currNode;
}
// shifting to the right child
currNode = currNode.rightNode;
}
}
}
return closestNode;
}
public static void main(String[] args)
{
Node root = newNode(10);
root.leftNode = newNode(12);
root.rightNode = newNode(3);
root.leftNode.leftNode = newNode(9);
root.leftNode.rightNode = newNode(11);
root.rightNode.leftNode = newNode(6);
root.rightNode.rightNode = newNode(8);
System.out.println("The closest element in the binary search tree is " + closestNode(root, 7).data);
}
}
Output:
The closest element in the binary search tree is 6
Complexity Analysis:
The Time complexity is O(N), where N is the Number of nodes of the given Binary Search Tree, and the Space complexity is O(1), which remains constant.
Approach: Using DFS (Depth First Search)
To search for the target node, traverse the BST beginning at the root. We should maintain a variable called min_dif and update it with the minimum sum and min_dif (current node->data, target node->data). We should move to the left of the current node if it is larger than the target node and to the right of the current node otherwise.
Algorithm:
Step 1: To store the minimum difference from the target node, initialize the mini_diff variable.
Step 2: Traverse the binary search tree from the root.
Step 3: Return of the pointer == NULL.
Step 4: Set mini_diffkey = 0 and end if pointer->key = k.
Step 5: Else if, mini_diff > abs(pointer->key – k), then mini_diff = abs(pointer->key – k) and mini_diff_key = pointer->key as the pointer to the minimal difference node, respectively.
Step6: Call pointer->left if k < pointer->key.
Step 7: Else Call pointer->right.
Implementation:
FileName: ClosestElementDFS.java
import java.io.*;
import java.util.*;
public class ClosestElementDFS
{
static int mini_diff, mini_diffkey;
// A binary tree node contains a key, a pointer to the child on the left, and a pointer to the child on the right.
static class Node
{
int key;
Node leftNode, rightNode;
};
// Function that creates a new node and assigns the given key to the left and right null pointers.
static Node newnode(int key)
{
Node node = new Node();
node.key = key;
node.leftNode = node.rightNode = null;
return (node);
}
// Function to identify the node with the lowest absolute difference with a given K.
// mini_diff -. Current minimal difference.
// mini_diffkey -. Node with the lowest absolute difference with K.
static void maxDiff(Node pointer, int k)
{
if (pointer == null)
return ;
// If the variable k is present
if (pointer.key == k)
{
mini_diffkey = k;
return;
}
// by verifying, update min_diff and min_diff_key
// value of the node at this moment
if (mini_diff > Math.abs(pointer.key - k))
{
mini_diff = Math.abs(pointer.key - k);
mini_diffkey = pointer.key;
}
// Go to the left subtree if k is smaller than pointer.key, else to the right subtree.
if (k < pointer.key)
maxDiff(pointer.leftNode, k);
else
maxDiff(pointer.rightNode, k);
}
// Wrapper over maxDiff()
static int maxDiffClosest(Node root, int k)
{
// Set the minimum difference initially
mini_diff = Integer.MAX_VALUE;
mini_diffkey = -1;
// Determine the value of the closest key, or mini_diffkey, in the tree with k.
maxDiff(root, k);
return mini_diffkey;
}
public static void main(String args[])
{
Node root = newnode(10);
root.leftNode = newnode(12);
root.rightNode = newnode(3);
root.leftNode.leftNode = newnode(9);
root.leftNode.rightNode = newnode(11);
root.rightNode.leftNode = newnode(6);
root.rightNode.rightNode = newnode(8);
int k = 9;
System.out.println( "The closest element in the binary search tree is " + maxDiffClosest(root, k));
}
}
Output:
The closest element in the binary search tree is 9
Complexity Analysis:
The Time complexity is O(H), where H is the height of the binary search tree, and the Space Complexity is O(1), which remains constant.