Binary Search Tree: Program to search the nearest node of a target

In this article, we will be going to find the nearest node to the given target value.
Here nearest node refers to the node having the least absolute difference between the target and the node value.

Before going to the approach of solving the problem, One should be familiar with the property of BST

•    All Nodes to the left of the current node has lower data than the current node
•    All Nodes to the right of the current node has greater data than the current node

So in the algorithm, we keep track of the minDiffNode which will be used to keep track of the node
having the minimum absolute difference and will be returned at last.

Algorithm

1. If the root of the BST is null then no node is present, so return null
2. Create a node named minDiffNode, and assign the root to it
3. Create a node named current, and assign the root to it
4. While the current is not null do:
   • Check if the absolute difference of current node data with the target is less than the absolute difference
     of minDiffNode data with the target, If less then make the minDiffNode as current
   • Compare the target with the data of current:
     • If the target is equal to data of current, then return current as the abs will be 0 and 0 is the least value possible
     • If the target is less than the data of current, then make current as left of current
     • Else make current as the right of the current
   • Return minDiffNode

Complexity

Average Case Time Complexity: O(LogN)
Worst Case Time Complexity: O(N)
Space Complexity: O(1)

The Time Complexity heavily depends on the structure of the given tree,
if the given tree is balanced then the time complexity will be O(logN) and
for a skew tree the time complexity will be O(N).

Space Complexity is constant as we do not use extra space.

Java Code

class BinarySearchTree {
        class Node {
          // Node class for Binary Search Tree
          int data;
          Node left, right;
        
          // Constructor to set the value of the node
          Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
          }
        }
        
        private Node root = null;
        
        // The function returns the first node which has closest absolute difference
        public Node getNearestNode(int target) {
          // The base case if the root is null
          if (root == null) {
            return null;
          }
        
          // Assign the value of the result as the root node
          Node minDiffNode = root;
        
          Node current = root;
          while (current != null) {
            if (Math.abs(current.data - target) < Math.abs(minDiffNode.data - target)) {
              minDiffNode = current;
            }
        
            // if target is equal to current data then return the current node
            // As the abs difference will be 0 which is lowest
            if (target == current.data) {
              return current;
            }else if(target < current.data) {
              current = current.left;
            }else{
              current = current.right;
            }
          }
        
          // Return the minDiffNode
          return minDiffNode;
        }
        
        // Insert array of num into the BST
        public void insertArray(int nums[]) {
          for (int i = 0; i < nums.length; i++) {
            insert(nums[i]);
          }
        }
        
        // Insert a value in BST Iteratively
        public void insert(int data) {
          // Check if root is null,
          // if null then create a node and make it root
          if (root == null) {
            root = new Node(data);
            return;
          }
        
          // Start traversing from the root and find the position of node to insert
          Node current = root;
          while (current != null) {
            if (data < current.data) {
              // Insert the node if the position is empty
              if (current.left == null) {
                current.left = new Node(data);
                return;
              }
              current = current.left;
            } else {
              if (current.right == null) {
                // Insert the node if the position is empty
                current.right = new Node(data);
                return;
              }
              current = current.right;
            }
          }
        }
        
        public static void main(String[] args) {
          int[] nums = { 8, 2, 6, 12, 11, 10 };
        
          BinarySearchTree bst = new BinarySearchTree();
          bst.insertArray(nums);
        
          System.out.println("Node closer to 0 is: " + bst.getNearestNode(0).data);
          System.out.println("Node closer to 4 is: " + bst.getNearestNode(4).data);
          System.out.println("Node closer to 8 is: " + bst.getNearestNode(8).data);
          System.out.println("Node closer to 13 is: " + bst.getNearestNode(13).data);
        }
        
       }

Output

Node closer to 0 is: 2
Node closer to 4 is: 2
Node closer to 8 is: 8
Node closer to 13 is: 12