Print BST keys in the given range

BST keys in the given range

Here given code implementation process.

//C Program 
//Print BST keys in the given range
#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
  }

}

//Print node of given range r1 and r2
void print_node(struct Node*root,int r1,int r2)
{
  if(root != NULL)
  {
    
    print_node(root->left,r1,r2);

    //Check if root node value is part of given range
    if(root->data >= r1 && root->data <= r2) 
    {
      //print node value
      printf("%3d",root->data );
    } 
     
    print_node(root->right,r1,r2);
  
  }
}
//This function are handle the request of show nodes between given range
void range_node(struct Node*root,int r1,int r2)
{
  if(root!=NULL)
  {
    printf("\n Node Between [%d-%d] Range is \n ",r1,r2);
    
    if(r1 > r2)
    {

      print_node(root,r2,r1);
    }
    else
    {
      print_node(root,r1,r2);
    }
  }
  else
  {
    printf("Empty BST\n");
  }
  printf("\n");
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
          5
       /    \
      3       9
     / \     / \
    2   4   8   11
   /       /    / \
  1       7    10  12  


  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,9); 
  add(&root,2); 
  add(&root,4); 
  add(&root,8); 
  add(&root,11); 
  add(&root,1); 
  add(&root,7); 
  add(&root,10); 
  add(&root,12);

  inorder(root);

  range_node(root,2,10);

  return 0;
}

Output

  1   2   3   4   5   7   8   9  10  11  12 
 Node Between [2-10] Range is 
   2  3  4  5  7  8  9 10
//C++ Program 
//Print BST keys in the given range
#include <iostream>
using namespace std;

//ure of Binary Search Tree node
struct Node
{
  int data;
  Node *left,*right; 
};

class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void print_node( Node*root,int r1,int r2);
  void range_node(int r1,int r2);
  void inorder( Node*root);
};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new 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
    {
       Node *find = root;

      //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
  {
    cout<<("Memory Overflow\n");
  }
}
void BST:: inorder( Node*root)
{
    if (root!=NULL)
    {
      
      inorder(root->left);
      cout<<"  "<<root->data;
      inorder(root->right);
    }
}



//Print node of given range r1 and r2
void BST:: print_node( Node*root,int r1,int r2)
{
  if (root != NULL)
  {
    
    print_node(root->left,r1,r2);
    //Check if root node value is part of given range
    if (root->data >= r1 && root->data <= r2) 
    {
      //print node value
      cout<<"  "<<root->data;
    } 
     
    print_node(root->right,r1,r2);
  
  }
}

//This function are handle the request of show nodes between given range
void BST:: range_node(int r1,int r2)
{
  if (root!=NULL)
  {
    cout<<"\n Node Between ["<<r1<<" - "<<r2 <<"] Range is \n ";
    
    if (r1 > r2)
    {
      print_node(root,r2,r1);
    }
    else
    {
      print_node(root,r1,r2);
    }
  }
  else
  {
    cout<<"Empty BST\n";
  }
  cout<<"\n";
}

int main()
{
  //Create object
  BST obj;

  //Add nodes in binary search tree
  /*
          5
       /    \
      3       9
     / \     / \
    2   4   8   11
   /       /    / \
  1       7    10  12 


  */                

  obj.add(5); 
  obj.add(3); 
  obj.add(9); 
  obj.add(2); 
  obj.add(4); 
  obj.add(8); 
  obj.add(11); 
  obj.add(1); 
  obj.add(7); 
  obj.add(10); 
  obj.add(12); 


  obj.inorder(obj.root);

  obj.range_node(2,10);

  return 0;
}

Output

  1  2  3  4  5  7  8  9  10  11  12
 Node Between [2 - 10] Range is 
   2  3  4  5  7  8  9  10
//Java program
//Print BST keys in the given range
public class BST
{
  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  //Class constructors
  BST()
  {
    root=null;

  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = 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 >= 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
    {
      System.out.println("Memory Overflow");
    }
  }
  public void   inorder( Node root)
  {
    if (root!=null)
    {

      inorder(root.left);
      System.out.print("  "+root.data);
      inorder(root.right);
    }
  }



  //Print node of given range r1 and r2
  public void   print_node( Node root,int r1,int r2)
  {
    if (root != null)
    {

      print_node(root.left,r1,r2);
      //Check if root node value is part of given range
      if (root.data >= r1 && root.data <= r2) 
      {
        //print node value
        System.out.print ("  "+root.data);
      } 

      print_node(root.right,r1,r2);

    }
  }

  //This function are handle the request of show nodes between given range
  public void   range_node(int r1,int r2)
  {
    if (root!=null)
    {
      System.out.print ("\n Node Between ["+r1+" - "+r2 +"] Range is \n ");
      
      if (r1 > r2)
      {
        print_node(root,r2,r1);
      }
      else
      {
        print_node(root,r1,r2);
      }
    }
    else
    {
      System.out.println("Empty BST");
    }
    System.out.println();
  }

  public static void main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
            5
         /    \
        3       9
       / \     / \
      2   4   8   11
     /       /    / \
    1       7    10  12 


    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(1); 
    obj.add(7); 
    obj.add(10); 
    obj.add(12); 


    obj.inorder(obj.root);

    obj.range_node(2,10);

  }
}

Output

  1  2  3  4  5  7  8  9  10  11  12
 Node Between [2 - 10] Range is 
   2  3  4  5  7  8  9  10
#Python Program 
#Print BST keys in the given range
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

    #Assign default value
    self.root=None
   



  #insert  element
  def add(self,data):

    #Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      #When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      #add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            #visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            #visit right sub-tree
            find = find.right
  
 
  def inorder(self,root) :

    if (root!=None) :

      self.inorder(root.left)
      print(root.data,end="  ")

      self.inorder(root.right)  
 
  #Print node of given range r1 and r2
  def   print_node(self,root, r1, r2) :

    if (root != None) :

      self.print_node(root.left,r1,r2)
      #Check if root node value is part of given range
      if (root.data >= r1  and  root.data <= r2)  :

        #print node value
        print(root.data,end="  ")

      self.print_node(root.right,r1,r2)
  #This function are handle the request of show nodes between given range
  def  range_node(self, r1, r2) :

    if (self.root!=None) :

      print("\n Node Between [",r1,"-",r2 ,"] Range is ")

      if (r1 > r2) :

        self.print_node(self.root,r2,r1)
      else :

        self.print_node(self.root,r1,r2)
    else :

      print("Empty BST\n")

    print("\n")


def main():

  #Make a object of BST class
  obj=  BST()

  #Add nodes in binary search tree
  #
  #          5
  #       /    \
  #      3       9
  #     / \     / \
  #    2   4   8   11
  #   /       /    / \
  #  1       7    10  12
  #  
  obj.add(5) 
  obj.add(3) 
  obj.add(9) 
  obj.add(2) 
  obj.add(4) 
  obj.add(8) 
  obj.add(11) 
  obj.add(1) 
  obj.add(7) 
  obj.add(10) 
  obj.add(12) 
  obj.inorder(obj.root)
  obj.range_node(2,10)

if __name__ =="__main__":
  main()

Output

1  2  3  4  5  7  8  9  10  11  12  
 Node Between [ 2 - 10 ] Range is 
2  3  4  5  7  8  9  10 
//C# program
//Print BST keys in the given range
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{

  public Node root;
  //Class constructors
  BST()
  {
    root=null;

  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = 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 >= 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
    {
      Console.WriteLine("Memory Overflow");
    }
  }
  public void   inorder( Node root)
  {
    if (root!=null)
    {

      inorder(root.left);
      Console.Write("  "+root.data);
      inorder(root.right);
    }
  }



  //Print node of given range r1 and r2
  public void   print_node( Node root,int r1,int r2)
  {
    if (root != null)
    {

      print_node(root.left,r1,r2);
      //Check if root node value is part of given range
      if (root.data >= r1 && root.data <= r2) 
      {
        //print node value
        Console.Write ("  "+root.data);
      } 

      print_node(root.right,r1,r2);

    }
  }

  //This function are handle the request of show nodes between given range
  public void   range_node(int r1,int r2)
  {
    if (root!=null)
    {
      Console.Write ("\n Node Between ["+r1+" - "+r2 +"] Range is \n ");

      if (r1 > r2)
      {
        print_node(root,r2,r1);
      }
      else
      {
        print_node(root,r1,r2);
      }
    }
    else
    {
      Console.WriteLine("Empty BST");
    }
    Console.WriteLine();
  }

  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /*
            5
         /    \
        3       9
       / \     / \
      2   4   8   11
     /       /    / \
    1       7    10  12 


    */                

    obj.add(5); 
    obj.add(3); 
    obj.add(9); 
    obj.add(2); 
    obj.add(4); 
    obj.add(8); 
    obj.add(11); 
    obj.add(1); 
    obj.add(7); 
    obj.add(10); 
    obj.add(12); 


    obj.inorder(obj.root);

    obj.range_node(2,10);

  }
}

Output

<?php
//Php program 
//Print BST keys in the given range
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;
  function __construct()
  {
    $root=NULL;
  }
  //Adding a new node in binary search tree
  public function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //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;
          }
        }
      }
    }

  }

  public function   inorder($root)
  {
    if ($root!=NULL)
    {
      $this->inorder($root->left);
      echo "  ".$root->data;
      $this->inorder($root->right);
    }
  }



  //Print node of given range r1 and r2
  public function  print_node($root, $r1, $r2)
  {
    if ($root != NULL)
    {

      $this->print_node($root->left,$r1,$r2);
      //Check if root node value is part of given range
      if ($root->data >= $r1 && $root->data <= $r2) 
      {
        //print node value
        echo "  ".$root->data;
      } 

      $this->print_node($root->right,$r1,$r2);

    }
  }

  //This function are handle the request of show nodes between given range
  public function   range_node( $r1, $r2)
  {
    if ($this->root!=NULL)
    {
      echo "\n Node Between [".$r1." - ".$r2 ."] Range is \n ";
      
      if ($r1 > $r2)
      {
        $this->print_node($this->root,$r2,$r1);
      }
      else
      {
        $this->print_node($this->root,$r1,$r2);
      }
    }
    else
    {
      echo "Empty BST\n";
    }
    echo "\n";
  }


}
function main()
{
  //Make a object of BST class
  $obj= new BST();


  //Add nodes in binary search tree
  /*
          5
       /    \
      3       9
     / \     / \
    2   4   8   11
   /       /    / \
  1       7    10  12 


  */                

  $obj->add(5); 
  $obj->add(3); 
  $obj->add(9); 
  $obj->add(2); 
  $obj->add(4); 
  $obj->add(8); 
  $obj->add(11); 
  $obj->add(1); 
  $obj->add(7); 
  $obj->add(10); 
  $obj->add(12); 


  $obj->inorder($obj->root);

  $obj->range_node(2,10);


}
main();
?>

Output

  1  2  3  4  5  7  8  9  10  11  12
 Node Between [2 - 10] Range is 
   2  3  4  5  7  8  9  10


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







© 2021, kalkicode.com, All rights reserved