Skip to main content

Find the closest element in Binary Search Tree

Find closest element in BST node

Here given code implementation process.

//C Program 
//Find the closest element in Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

int find_difference(int a,int b)
{
   a=a-b;

  if(a<0)
  {
    a=-a;
  }
  return a;
}
//Get the minimum difference of  three nodes 
int compare_node(struct Node *head,
  struct Node *left_p,
  struct Node *right_p,
  int element)
{

  int result=0,a=0,b=0,c=0;

  if(left_p != NULL && right_p != NULL)
  {
    a=find_difference(left_p->data,element);
    b=find_difference(right_p->data,element);
    c=find_difference(head->data,element);
    //get min difference element

      if((a<b)&&(a<c))
    {
      result = left_p->data;
    }
    else if(b<c && b<a)
    {
      result = right_p->data ;
    }
    else
    {
      result=head->data;
    }
   
  }
  else if(left_p!=NULL)
  {
    a=find_difference(left_p->data,element);
    c=find_difference(head->data,element);
    if(c<a)
    {
      result = head->data;
    }
    else
    {
      result = left_p->data ;
    }
  

  }
  else if(right_p != NULL)
  {
    b=find_difference(right_p->data,element);
    c=find_difference(head->data,element);
  
    if(c<a)
    {
      result = head->data;
    }
    else
    {
      result = right_p->data ;
    }

  }
  else
  {
    result=head->data;
  }
  return result;
}
void find_node(struct Node *root,
  struct Node *left_p,
  struct Node *right_p,
  int element)
{

    if(root!=NULL)
    {
     
      if(root->data==element)
      {
        printf("Node %d closest element  %d\n",element ,root->data );
      }
      else if(root->data > element)
      {
        if(root->left!=NULL)
        {
          find_node(root->left,left_p,root,element);
        }
        else
        {
          int result=compare_node(root,left_p,right_p,element);
          printf("Node %d closest element  %d\n",element ,result );
        }
      }
      else
      {
        if(root->right!=NULL)
        {
          find_node(root->right,root,right_p,element);
        }
        else
        {
          int result=compare_node(root,left_p,right_p,element);
          printf("Node %d closest element  %d\n",element ,result );
        }
        
      }
    }
  


}
void find_elements(struct Node *root,int element)
{

  if(root!=NULL)
  {
     find_node(root,NULL,NULL,element);
  }
  else
  {
    printf("\nEmpty BST");
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree

  /*
         10
       /   \
      3     19
     / \   /  \
    1   4  14  50
   / \     
 -3   2          

  */



  add(&root,10); 
  add(&root,3); 
  add(&root,19); 
  add(&root,1); 
  add(&root,4);
  add(&root,-3); 
  add(&root,2); 
  add(&root,14); 
  add(&root,50); 

  //Test case
  find_elements(root,4);
  find_elements(root,17);
  find_elements(root,11);
  find_elements(root,25);
  find_elements(root,16);


  return 0;
}

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
/*
 C++ Program
 Find the closest element in Binary Search Tree
*/

#include<iostream>

using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;
  Node(int value) {
    this->data = value;
    this->left = NULL;
    this->right = NULL;
  }
};
class BinarySearchTree {
  public:
  Node *root;
  int result;
  BinarySearchTree() {
    this->root = NULL;
    this->result = 0;
  }
  void add(int value) {
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        this->root = new_node;
      } else {
        Node *find = this->root;
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              break;
            } else {
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              break;
            } else {
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "\nMemory Overflow\n";
    }
  }
  int find_difference(int a, int b) {
    a = a - b;
    if (a < 0) {
      a = -a;
    }
    return a;
  }
  void compare_node(Node *head, Node *left_p, Node *right_p, int element) {
    int a = 0, b = 0, c = 0;
    if (left_p != NULL && right_p != NULL) {
      a = this->find_difference(left_p->data, element);
      b = this->find_difference(right_p->data, element);
      c = this->find_difference(head->data, element);
      if ((a < b) && (a < c)) {
        this->result = left_p->data;
      } else
      if (b < c && b < a) {
        this->result = right_p->data;
      } else {
        this->result = head->data;
      }
    } else
    if (left_p != NULL) {
      a = this->find_difference(left_p->data, element);
      c = this->find_difference(head->data, element);
      if (c < a) {
        this->result = head->data;
      } else {
        this->result = left_p->data;
      }
    } else
    if (right_p != NULL) {
      b = this->find_difference(right_p->data, element);
      c = this->find_difference(head->data, element);
      if (c < a) {
        this->result = head->data;
      } else {
        this->result = right_p->data;
      }
    } else {
      this->result = head->data;
    }
  }
  void find_node(Node *head, Node *left_p, Node *right_p, int element) {
    if (head != NULL) {
      this->result = 0;
      if (head->data == element) {
        cout << "\nNode " << element << " closest element is " << head->data;
      } else
      if (head->data > element) {
        if (head->left != NULL) {
          this->find_node(head->left, left_p, head, element);
        } else {
          this->compare_node(head, left_p, right_p, element);
          cout << "\nNode " << element << " closest element is " << this->result;
        }
      } else {
        if (head->right != NULL) {
          this->find_node(head->right, head, right_p, element);
        } else {
          this->compare_node(head, left_p, right_p, element);
          cout << "\nNode " << element << " closest element is " << this->result;
        }
      }
    }
  }
  void find_elements(int element) {
    if (this->root != NULL) {
      this->find_node(this->root, NULL, NULL, element);
    } else {
      cout << "\nEmpty BST";
    }
  }
};

int main() {
  BinarySearchTree obj;
  /*
         10
       /   \
      3     19
     / \   /  \
    1   4  14  50
   / \     
 -3   2          

  */
  obj.add(10);
  obj.add(3);
  obj.add(19);
  obj.add(1);
  obj.add(4);
  obj.add(-3);
  obj.add(2);
  obj.add(14);
  obj.add(50);
  obj.find_elements(4);
  obj.find_elements(17);
  obj.find_elements(11);
  obj.find_elements(25);
  obj.find_elements(16);
  return 0;
}

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
//Java program
//Find the closest element in Binary Search Tree

class Node {
  public int data;
  public Node left;
  public Node right;

  public Node(int value) {
    data = value;
    left = null;
    right = null;
  }
}
public class BinarySearchTree {


  public Node root;
  public int result;

  BinarySearchTree() {
    root = null;
    result=0;
  }
  //insert a node in BST
  public void add(int value) {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node(value);

    if (new_node != null) {
      if (root == null) {
        //When adds a first node in binary tree
        root = new_node;
      } else {
        Node find = root;

        //add new node to proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              break;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              break;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      System.out.print("\nMemory Overflow\n");
    }
  }
  public int find_difference(int a, int b) {
    a = a - b;

    if (a < 0) {
      a = -a;
    }
    return a;
  }
  //Get the minimum difference of  three nodes 
  public void compare_node(Node head,
    Node left_p,
    Node right_p,
    int element) {

    int a = 0, b = 0, c = 0;

    if (left_p != null && right_p != null) {
      a = find_difference(left_p.data, element);
      b = find_difference(right_p.data, element);
      c = find_difference(head.data, element);
      //get min difference element

      if ((a < b) && (a < c)) {
        this.result = left_p.data;
      } else if (b < c && b < a) {
        this.result = right_p.data;
      } else {
        this.result = head.data;
      }

    } else if (left_p != null) {
      a = find_difference(left_p.data, element);
      c = find_difference(head.data, element);
      if (c < a) {
        this.result = head.data;
      } else {
        this.result = left_p.data;
      }


    } else if (right_p != null) {
      b = find_difference(right_p.data, element);
      c = find_difference(head.data, element);

      if (c < a) {
        this.result = head.data;
      } else {
        this.result = right_p.data;
      }

    } else {
      this.result = head.data;
    }

  }
  public void find_node(Node head,
    Node left_p,
    Node right_p,
    int element) {

    if (head != null) {
      this.result = 0;
      if (head.data == element) {
        System.out.print("\nNode " + element + " closest element is " + head.data);
      }
      else if (head.data > element) {
        if (head.left != null) {
          find_node(head.left, left_p, head, element);
        } else {
          compare_node(head, left_p, right_p, element);
          System.out.print("\nNode " + element + " closest element is " + this.result);
        }
      } else {
        if (head.right != null) {
          find_node(head.right, head, right_p, element);
        } else {
          compare_node(head, left_p, right_p, element);
          System.out.print("\nNode " + element + " closest element is " + this.result);
        }

      }
    }



  }
  public void find_elements(int element) {

    if (root != null) {
      find_node(root, null, null, element);
    } else {
      System.out.print("\nEmpty BST");
    }
  }
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();


    //Add nodes in binary search tree

    /*
             10
           /   \
          3     19
         / \   /  \
        1   4  14  50
       / \     
     -3   2          

    */



    obj.add(10);
    obj.add(3);
    obj.add(19);
    obj.add(1);
    obj.add(4);
    obj.add(-3);
    obj.add(2);
    obj.add(14);
    obj.add(50);

    //Test case
    obj.find_elements(4);
    obj.find_elements(17);
    obj.find_elements(11);
    obj.find_elements(25);
    obj.find_elements(16);


  }
}

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
//C# program
//Find the closest element in Binary Search Tree
using System;
public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int value) {
		data = value;
		left = null;
		right = null;
	}
}
public class BinarySearchTree {


	public Node root;
	public int result;

	BinarySearchTree() {
		root = null;
		result=0;
	}
	//insert a node in BST
	public void add(int value) {
		//Create a dynamic node of binary search tree 
		Node new_node = new Node(value);

		if (new_node != null) {
			if (root == null) {
				//When adds a first node in binary tree
				root = new_node;
			} else {
				Node find = root;

				//add new node to proper position
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							//visit left sub-tree
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							//visit right sub-tree
							find = find.right;
						}
					}
				}
			}
		} else {
			Console.Write("\nMemory Overflow\n");
		}
	}
	public int find_difference(int a, int b) {
		a = a - b;

		if (a < 0) {
			a = -a;
		}
		return a;
	}
	//Get the minimum difference of  three nodes 
	public void compare_node(Node head,
		Node left_p,
		Node right_p,
		int element) {

		int a = 0, b = 0, c = 0;

		if (left_p != null && right_p != null) {
			a = find_difference(left_p.data, element);
			b = find_difference(right_p.data, element);
			c = find_difference(head.data, element);
			//get min difference element

			if ((a < b) && (a < c)) {
				this.result = left_p.data;
			} else if (b < c && b < a) {
				this.result = right_p.data;
			} else {
				this.result = head.data;
			}

		} else if (left_p != null) {
			a = find_difference(left_p.data, element);
			c = find_difference(head.data, element);
			if (c < a) {
				this.result = head.data;
			} else {
				this.result = left_p.data;
			}


		} else if (right_p != null) {
			b = find_difference(right_p.data, element);
			c = find_difference(head.data, element);

			if (c < a) {
				this.result = head.data;
			} else {
				this.result = right_p.data;
			}

		} else {
			this.result = head.data;
		}

	}
	public void find_node(Node head,
		Node left_p,
		Node right_p,
		int element) {

		if (head != null) {
			this.result = 0;
			if (head.data == element) {
				Console.Write("\nNode " + element + " closest element is " + head.data);
			}
			else if (head.data > element) {
				if (head.left != null) {
					find_node(head.left, left_p, head, element);
				} else {
					compare_node(head, left_p, right_p, element);
					Console.Write("\nNode " + element + " closest element is " + this.result);
				}
			} else {
				if (head.right != null) {
					find_node(head.right, head, right_p, element);
				} else {
					compare_node(head, left_p, right_p, element);
					Console.Write("\nNode " + element + " closest element is " + this.result);
				}

			}
		}



	}
	public void find_elements(int element) {

		if (root != null) {
			find_node(root, null, null, element);
		} else {
			Console.Write("\nEmpty BST");
		}
	}
	public static void Main(String[] args) {

		BinarySearchTree obj = new BinarySearchTree();


		//Add nodes in binary search tree

		/*
             10
           /   \
          3     19
         / \   /  \
        1   4  14  50
       / \     
     -3   2          

    */



		obj.add(10);
		obj.add(3);
		obj.add(19);
		obj.add(1);
		obj.add(4);
		obj.add(-3);
		obj.add(2);
		obj.add(14);
		obj.add(50);

		//Test case
		obj.find_elements(4);
		obj.find_elements(17);
		obj.find_elements(11);
		obj.find_elements(25);
		obj.find_elements(16);


	}
}

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
# Python 3 Program
# Find the closest element in Binary Search Tree

class Node :

  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :

  def __init__(self) :
    self.root = None
    self.result = 0
  
  def add(self, value) :
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        self.root = new_node
      else :
        find = self.root
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              break
            else :
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              break
            else :
              find = find.right
            
          
        
      
    else :
      print("\nMemory Overflow\n")
    
  
  def find_difference(self, a, b) :
    a = a - b
    if (a < 0) :
      a = -a
    
    return a
  
  def compare_node(self, head, left_p, right_p, element) :
    a = 0
    b = 0
    c = 0
    if (left_p != None and right_p != None) :
      a = self.find_difference(left_p.data, element)
      b = self.find_difference(right_p.data, element)
      c = self.find_difference(head.data, element)
      if ((a < b) and(a < c)) :
        self.result = left_p.data
      elif (b < c and b < a) :
        self.result = right_p.data
      else :
        self.result = head.data
      
    elif (left_p != None) :
      a = self.find_difference(left_p.data, element)
      c = self.find_difference(head.data, element)
      if (c < a) :
        self.result = head.data
      else :
        self.result = left_p.data
      
    elif (right_p != None) :
      b = self.find_difference(right_p.data, element)
      c = self.find_difference(head.data, element)
      if (c < a) :
        self.result = head.data
      else :
        self.result = right_p.data
      
    else :
      self.result = head.data
    
  
  def find_node(self, head, left_p, right_p, element) :
    if (head != None) :
      self.result = 0
      if (head.data == element) :
        print("Node ", element ," closest element is ", head.data)
      elif (head.data > element) :
        if (head.left != None) :
          self.find_node(head.left, left_p, head, element)
        else :
          self.compare_node(head, left_p, right_p, element)
          print("Node ", element ," closest element is ", self.result)
        
      else :
        if (head.right != None) :
          self.find_node(head.right, head, right_p, element)
        else :
          self.compare_node(head, left_p, right_p, element)
          print("Node ", element ," closest element is ", self.result)
        
      
    
  
  def find_elements(self, element) :
    if (self.root != None) :
      self.find_node(self.root, None, None, element)
    else :
      print("\nEmpty BST")
    
  
def main() :
  obj = BinarySearchTree()
  #
  #         10
  #       /   \
  #      3     19
  #     / \   /  \
  #    1   4  14  50
  #   / \
  # -3   2
  #  
  obj.add(10)
  obj.add(3)
  obj.add(19)
  obj.add(1)
  obj.add(4)
  obj.add(-3)
  obj.add(2)
  obj.add(14)
  obj.add(50)
  obj.find_elements(4)
  obj.find_elements(17)
  obj.find_elements(11)
  obj.find_elements(25)
  obj.find_elements(16)


if __name__ == "__main__":
  main()

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
# Ruby Program
# Find the closest element in Binary Search Tree

class Node 
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(value) 
		@data = value
		@left = nil
		@right = nil
	end
end

class BinarySearchTree 
	attr_reader :root, :result
	attr_accessor :root, :result
	def initialize() 
		@root = nil
		@result = 0
	end
	def add(value) 
		new_node = Node.new(value)
		if (new_node != nil) 
			if (@root == nil) 
				@root = new_node
			else 
				find = @root
				while (find != nil) 
					if (find.data >= value) 
						if (find.left == nil) 
							find.left = new_node
							break
						else 
							find = find.left
						end
					else 
						if (find.right == nil) 
							find.right = new_node
							break
						else 
							find = find.right
						end
					end
				end
			end
		else 
			print("\nMemory Overflow\n")
		end
	end
	def find_difference(a, b) 
		a = a - b
		if (a < 0) 
			a = -a
		end
		return a
	end
	def compare_node(head, left_p, right_p, element) 
		a = 0
		b = 0
		c = 0
		if (left_p != nil and right_p != nil) 
			a = self.find_difference(left_p.data, element)
			b = self.find_difference(right_p.data, element)
			c = self.find_difference(head.data, element)
			if ((a < b) and(a < c)) 
				self.result = left_p.data
			elsif (b < c and b < a) 
				self.result = right_p.data
			else 
				self.result = head.data
			end
		elsif (left_p != nil) 
			a = self.find_difference(left_p.data, element)
			c = self.find_difference(head.data, element)
			if (c < a) 
				self.result = head.data
			else 
				self.result = left_p.data
			end
		elsif (right_p != nil) 
			b = self.find_difference(right_p.data, element)
			c = self.find_difference(head.data, element)
			if (c < a) 
				self.result = head.data
			else 
				self.result = right_p.data
			end
		else 
			self.result = head.data
		end
	end
	def find_node(head, left_p, right_p, element) 
		if (head != nil) 
			self.result = 0
			if (head.data == element) 
				print("\nNode ", element ," closest element is ", head.data)
			elsif (head.data > element) 
				if (head.left != nil) 
					self.find_node(head.left, left_p, head, element)
				else 
					self.compare_node(head, left_p, right_p, element)
					print("\nNode ", element ," closest element is ", self.result)
				end
			else 
				if (head.right != nil) 
					self.find_node(head.right, head, right_p, element)
				else 
					self.compare_node(head, left_p, right_p, element)
					print("\nNode ", element ," closest element is ", self.result)
				end
			end
		end
	end
	def find_elements(element) 
		if (@root != nil) 
			self.find_node(@root, nil, nil, element)
		else 
			print("\nEmpty BST")
		end
	end
end

def main() 
	obj = BinarySearchTree.new()
	#
	#         10
	#       /   \
	#      3     19
	#     / \   /  \
	#    1   4  14  50
	#   / \
	# -3   2
	#  
	obj.add(10)
	obj.add(3)
	obj.add(19)
	obj.add(1)
	obj.add(4)
	obj.add(-3)
	obj.add(2)
	obj.add(14)
	obj.add(50)
	obj.find_elements(4)
	obj.find_elements(17)
	obj.find_elements(11)
	obj.find_elements(25)
	obj.find_elements(16)
end

main()

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
<?php
/*
 Php Program
 Find the closest element in Binary Search Tree
*/

class Node {
  public $data;
  public $left;
  public $right;

  function __construct($value) {
    $this->data = $value;
    $this->left = null;
    $this->right = null;
  }
}
class BinarySearchTree {
  public $root;
  public $result;

  function __construct() {
    $this->root = null;
    $this->result = 0;
  }
  public  function add($value) {
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        $this->root = $new_node;
      } else {
        $find = $this->root;
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              break;
            } else {
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              break;
            } else {
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("\nMemory Overflow\n");
    }
  }
  public  function find_difference($a, $b) {
    $a = $a - $b;
    if ($a < 0) {
      $a = -$a;
    }
    return $a;
  }
  public  function compare_node($head, $left_p, $right_p, $element) {
    $a = 0;
    $b = 0;
    $c = 0;
    if ($left_p != null && $right_p != null) {
      $a = $this->find_difference($left_p->data, $element);
      $b = $this->find_difference($right_p->data, $element);
      $c = $this->find_difference($head->data, $element);
      if (($a < $b) && ($a < $c)) {
        $this->result = $left_p->data;
      } else
      if ($b < $c && $b < $a) {
        $this->result = $right_p->data;
      } else {
        $this->result = $head->data;
      }
    } else
    if ($left_p != null) {
      $a = $this->find_difference($left_p->data, $element);
      $c = $this->find_difference($head->data, $element);
      if ($c < $a) {
        $this->result = $head->data;
      } else {
        $this->result = $left_p->data;
      }
    } else
    if ($right_p != null) {
      $b = $this->find_difference($right_p->data, $element);
      $c = $this->find_difference($head->data, $element);
      if ($c < $a) {
        $this->result = $head->data;
      } else {
        $this->result = $right_p->data;
      }
    } else {
      $this->result = $head->data;
    }
  }
  public  function find_node($head, $left_p, $right_p, $element) {
    if ($head != null) {
      $this->result = 0;
      if ($head->data == $element) {
        echo("\nNode ". $element ." closest element is ". $head->data);
      } else
      if ($head->data > $element) {
        if ($head->left != null) {
          $this->find_node($head->left, $left_p, $head, $element);
        } else {
          $this->compare_node($head, $left_p, $right_p, $element);
          echo("\nNode ". $element ." closest element is ". $this->result);
        }
      } else {
        if ($head->right != null) {
          $this->find_node($head->right, $head, $right_p, $element);
        } else {
          $this->compare_node($head, $left_p, $right_p, $element);
          echo("\nNode ". $element ." closest element is ". $this->result);
        }
      }
    }
  }
  public  function find_elements($element) {
    if ($this->root != null) {
      $this->find_node($this->root, null, null, $element);
    } else {
      echo("\nEmpty BST");
    }
  }
}
function main() {
  $obj = new BinarySearchTree();
  /*
         10
       /   \
      3     19
     / \   /  \
    1   4  14  50
   / \     
 -3   2          

  */
  $obj->add(10);
  $obj->add(3);
  $obj->add(19);
  $obj->add(1);
  $obj->add(4);
  $obj->add(-3);
  $obj->add(2);
  $obj->add(14);
  $obj->add(50);
  $obj->find_elements(4);
  $obj->find_elements(17);
  $obj->find_elements(11);
  $obj->find_elements(25);
  $obj->find_elements(16);
}
main();

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
/*
 Node Js Program
 Find the closest element in Binary Search Tree
*/

class Node {
	
	constructor(value) {
		this.data = value;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree {
	
	constructor() {
		this.root = null;
		this.result = 0;
	}
	add(value) {
		var new_node = new Node(value);
		if (new_node != null) {
			if (this.root == null) {
				this.root = new_node;
			} else {
				var find = this.root;
				while (find != null) {
					if (find.data >= value) {
						if (find.left == null) {
							find.left = new_node;
							break;
						} else {
							find = find.left;
						}
					} else {
						if (find.right == null) {
							find.right = new_node;
							break;
						} else {
							find = find.right;
						}
					}
				}
			}
		} else {
			process.stdout.write("\nMemory Overflow\n");
		}
	}
	find_difference(a, b) {
		a = a - b;
		if (a < 0) {
			a = -a;
		}
		return a;
	}
	compare_node(head, left_p, right_p, element) {
		var a = 0;
		var b = 0;
		var c = 0;
		if (left_p != null && right_p != null) {
			a = this.find_difference(left_p.data, element);
			b = this.find_difference(right_p.data, element);
			c = this.find_difference(head.data, element);
			if ((a < b) && (a < c)) {
				this.result = left_p.data;
			} else
			if (b < c && b < a) {
				this.result = right_p.data;
			} else {
				this.result = head.data;
			}
		} else
		if (left_p != null) {
			a = this.find_difference(left_p.data, element);
			c = this.find_difference(head.data, element);
			if (c < a) {
				this.result = head.data;
			} else {
				this.result = left_p.data;
			}
		} else
		if (right_p != null) {
			b = this.find_difference(right_p.data, element);
			c = this.find_difference(head.data, element);
			if (c < a) {
				this.result = head.data;
			} else {
				this.result = right_p.data;
			}
		} else {
			this.result = head.data;
		}
	}
	find_node(head, left_p, right_p, element) {
		if (head != null) {
			this.result = 0;
			if (head.data == element) {
				process.stdout.write("\nNode " + element + " closest element is " + head.data);
			} else
			if (head.data > element) {
				if (head.left != null) {
					this.find_node(head.left, left_p, head, element);
				} else {
					this.compare_node(head, left_p, right_p, element);
					process.stdout.write("\nNode " + element + " closest element is " + this.result);
				}
			} else {
				if (head.right != null) {
					this.find_node(head.right, head, right_p, element);
				} else {
					this.compare_node(head, left_p, right_p, element);
					process.stdout.write("\nNode " + element + " closest element is " + this.result);
				}
			}
		}
	}
	find_elements(element) {
		if (this.root != null) {
			this.find_node(this.root, null, null, element);
		} else {
			process.stdout.write("\nEmpty BST");
		}
	}
}

function main() {
	var obj = new BinarySearchTree();
	/*
	         10
	       /   \
	      3     19
	     / \   /  \
	    1   4  14  50
	   / \     
	 -3   2          

    */
	obj.add(10);
	obj.add(3);
	obj.add(19);
	obj.add(1);
	obj.add(4);
	obj.add(-3);
	obj.add(2);
	obj.add(14);
	obj.add(50);
	obj.find_elements(4);
	obj.find_elements(17);
	obj.find_elements(11);
	obj.find_elements(25);
	obj.find_elements(16);
}

main();

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14
/*
 Swift 4 Program
 Find the closest element in Binary Search Tree
*/

class Node {
  var data: Int;
  var left: Node? ;
  var right: Node? ;
  init(_ value: Int) {
    self.data = value;
    self.left = nil;
    self.right = nil;
  }
}
class BinarySearchTree {
  var root: Node? ;
  var result: Int;
  init() {
    self.root = nil;
    self.result = 0;
  }
  func add(_ value: Int) {
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              break;
            } else {
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              break;
            } else {
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("\nMemory Overflow\n");
    }
  }
  func find_difference(_ a: Int, _ b: Int) -> Int {
    var get_a = a;

    get_a = a - b;
    if (get_a < 0) {
      get_a = -get_a;
    }
    return get_a;
  }
  func compare_node(_ head: Node? , _ left_p : Node? , _ right_p : Node? , _ element : Int) {
    var a: Int = 0;
    var b = 0;
    var c = 0;
    if (left_p != nil && right_p != nil) {
      a = self.find_difference(left_p!.data, element);
      b = self.find_difference(right_p!.data, element);
      c = self.find_difference(head!.data, element);
      if ((a < b) && (a < c)) {
        self.result = left_p!.data;
      } else
      if (b < c && b < a) {
        self.result = right_p!.data;
      } else {
        self.result = head!.data;
      }
    } else
    if (left_p != nil) {
      a = self.find_difference(left_p!.data, element);
      c = self.find_difference(head!.data, element);
      if (c < a) {
        self.result = head!.data;
      } else {
        self.result = left_p!.data;
      }
    } else
    if (right_p != nil) {
      b = self.find_difference(right_p!.data, element);
      c = self.find_difference(head!.data, element);
      if (c < a) {
        self.result = head!.data;
      } else {
        self.result = right_p!.data;
      }
    } else {
      self.result = head!.data;
    }
  }
  func find_node(_ head: Node? , _ left_p : Node? , _ right_p : Node? , _ element : Int) {
    if (head != nil) {
      self.result = 0;
      if (head!.data == element) {
        print("Node ", element ," closest element is ", head!.data);
      } else
      if (head!.data > element) {
        if (head!.left != nil) {
          self.find_node(head!.left, left_p, head, element);
        } else {
          self.compare_node(head, left_p, right_p, element);
          print("Node ", element ," closest element is ", self.result);
        }
      } else {
        if (head!.right != nil) {
          self.find_node(head!.right, head, right_p, element);
        } else {
          self.compare_node(head, left_p, right_p, element);
          print("Node ", element ," closest element is ", self.result);
        }
      }
    }
  }
  func find_elements(_ element: Int) {
    if (self.root != nil) {
      self.find_node(self.root, nil, nil, element);
    } else {
      print("\nEmpty BST");
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
         10
       /   \
      3     19
     / \   /  \
    1   4  14  50
   / \     
 -3   2          

  */
  obj.add(10);
  obj.add(3);
  obj.add(19);
  obj.add(1);
  obj.add(4);
  obj.add(-3);
  obj.add(2);
  obj.add(14);
  obj.add(50);
  obj.find_elements(4);
  obj.find_elements(17);
  obj.find_elements(11);
  obj.find_elements(25);
  obj.find_elements(16);
}
main();

Output

Node 4 closest element  4
Node 17 closest element  19
Node 11 closest element  10
Node 25 closest element  19
Node 16 closest element  14




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment