Posted on by Kalkicode
Code Binary Search Tree

Count BST nodes that lie in a given range

Counting BST nodes that lie in a given range

Here given code implementation process.

//C Program 
//Count BST nodes that lie in a 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
  }

}
void count_element(struct Node*root,
  int *counter,int first,int second)
{
  
  if(root!=NULL)
  {
    if(root->data >= first && root->data <=second)
    {
      (*counter)++;
    }
    count_element(root->left,counter,first,second);

    count_element(root->right,counter,first,second);


  }
 
 
}
void counter_nodes(struct Node*root,int first,int second)
{
  if(root != NULL)
  {
    
   int counter=0;
   if(first < second)
   {
     count_element(root,&counter,first,second);
   }
   else
   {
     count_element(root,&counter,second,first);
   }
  
    printf("[%d,%d] => %d\n",first,second,counter );
   
  }
  else
  {
    printf("Empty BST\n");
  }
}

int main(){
    
  struct Node*root = NULL;

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


  */                


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

    
  return 0;
}

Output

[1,10] => 8
/*
 C++ Program
 Count BST nodes that lie in a given range
*/

#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 counter;
  BinarySearchTree() {
    this->root = NULL;
    this->counter = 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";
    }
  }
  void count_element(Node *head, int first, int second) {
    if (head != NULL) {
      if (head->data >= first && head->data <= second) {
        this->counter++;
      }
      this->count_element(head->left, first, second);
      this->count_element(head->right, first, second);
    }
  }
  void counter_nodes(int first, int second) {
    if (this->root != NULL) {
      this->counter = 0;
      if (first < second) {
        this->count_element(this->root, first, second);
      } else {
        this->count_element(this->root, second, first);
      }
      cout << "[" << first << "," << second << "] => " << this->counter << "\n";
    } else {
      cout << "\nEmpty BST\n";
    }
  }
};

int main() {
  BinarySearchTree obj;
  /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


  */  
  obj.add(6);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(5);
  obj.add(7);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(12);
  obj.add(4);
  obj.counter_nodes(1, 10);
  return 0;
}

Output

[1,10] => 8
//Java program
//Count BST nodes that lie in a given range

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 counter;
  BinarySearchTree() {
    root = null;
    counter = 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 void  count_element(Node head,
  int first,int second)
{
  
  if(head!=null)
  {
    if(head.data >= first && head.data <=second)
    {
      this.counter++;
    }
    count_element(head.left,first,second);

    count_element(head.right,first,second);


  }
 
 
}
public void  counter_nodes(int first,int second)
{
  if(root != null)
  {
    
   this.counter=0;
   if(first < second)
   {
     count_element(root,first,second);
   }
   else
   {
     count_element(root,second,first);
   }
  
   System.out.print("["+first+","+second+"] => "+this.counter+"\n" );
   
  }
  else
  {
    System.out.print("\nEmpty BST\n");
  }
}
  public static void main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
    //Add nodes in binary search tree
  /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


  */                


    obj.add(6); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(5); 
    obj.add(7); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 
    
    obj.add(12);
    obj.add(4);  
  
    obj.counter_nodes(1,10);

  }
}

Output

[1,10] => 8
//C# program
//Count BST nodes that lie in a given range
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 counter;
  BinarySearchTree() {
    root = null;
    counter = 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 void  count_element(Node head,
    int first,int second)
  {

    if(head!=null)
    {
      if(head.data >= first && head.data <=second)
      {
        this.counter++;
      }
      count_element(head.left,first,second);

      count_element(head.right,first,second);


    }


  }
  public void  counter_nodes(int first,int second)
  {
    if(root != null)
    {

      this.counter=0;
      if(first < second)
      {
        count_element(root,first,second);
      }
      else
      {
        count_element(root,second,first);
      }

      Console.Write("["+first+","+second+"] => "+this.counter+"\n" );

    }
    else
    {
      Console.Write("\nEmpty BST\n");
    }
  }
  public static void Main(String[] args) {

    BinarySearchTree obj = new BinarySearchTree();
    //Add nodes in binary search tree
    /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


  */                


    obj.add(6); 
    obj.add(3); 
    obj.add(9); 
    obj.add(1); 
    obj.add(5); 
    obj.add(7); 
    obj.add(11); 
    obj.add(-3); 
    obj.add(2); 

    obj.add(12);
    obj.add(4);  

    obj.counter_nodes(1,10);

  }
}

Output

[1,10] => 8
# Python 3 Program
# Count BST nodes that lie in a given range

class Node :

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

class BinarySearchTree :
  
  def __init__(self) :
    self.root = None
    self.counter = 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 count_element(self, head, first, second) :
    if (head != None) :
      if (head.data >= first and head.data <= second) :
        self.counter += 1
      
      self.count_element(head.left, first, second)
      self.count_element(head.right, first, second)
    
  
  def counter_nodes(self, first, second) :
    if (self.root != None) :
      self.counter = 0
      if (first < second) :
        self.count_element(self.root, first, second)
      else :
        self.count_element(self.root, second, first)
      
      print("[", first ,",", second ,"] => ", self.counter)
    else :
      print("\nEmpty BST\n")
    
  
def main() :
  obj = BinarySearchTree()
  #
  #              6
  #            /    \
  #           /      \
  #          3        9
  #         /  \      / \
  #        1    5    7   11
  #       / \   /         \
  #     -3  2  4           12
  #  
  obj.add(6)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(5)
  obj.add(7)
  obj.add(11)
  obj.add(-3)
  obj.add(2)
  obj.add(12)
  obj.add(4)
  obj.counter_nodes(1, 10)
  

if __name__ == "__main__":
  main()

Output

[1,10] => 8
# Ruby Program
# Count BST nodes that lie in a given range

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, :counter
  attr_accessor :root, :counter
  def initialize() 
    @root = nil
    @counter = 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 count_element(head, first, second) 
    if (head != nil) 
      if (head.data >= first and head.data <= second) 
        self.counter += 1
      end
      self.count_element(head.left, first, second)
      self.count_element(head.right, first, second)
    end
  end
  def counter_nodes(first, second) 
    if (@root != nil) 
      self.counter = 0
      if (first < second) 
        self.count_element(@root, first, second)
      else 
        self.count_element(@root, second, first)
      end
      print("[", first ,",", second ,"] => ", self.counter ,"\n")
    else 
      print("\nEmpty BST\n")
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  #
  #              6
  #            /    \
  #           /      \
  #          3        9
  #         /  \      / \
  #        1    5    7   11
  #       / \   /         \
  #     -3  2  4           12
  #  
  obj.add(6)
  obj.add(3)
  obj.add(9)
  obj.add(1)
  obj.add(5)
  obj.add(7)
  obj.add(11)
  obj.add(-3)
  obj.add(2)
  obj.add(12)
  obj.add(4)
  obj.counter_nodes(1, 10)
end


main()

Output

[1,10] => 8
<?php
/*
 Php Program
 Count BST nodes that lie in a given range
*/

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 $counter;

  function __construct() {
    $this->root = null;
    $this->counter = 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 count_element($head, $first, $second) {
    if ($head != null) {
      if ($head->data >= $first && $head->data <= $second) {
        $this->counter++;
      }
      $this->count_element($head->left, $first, $second);
      $this->count_element($head->right, $first, $second);
    }
  }
  public  function counter_nodes($first, $second) {
    if ($this->root != null) {
      $this->counter = 0;
      if ($first < $second) {
        $this->count_element($this->root, $first, $second);
      } else {
        $this->count_element($this->root, $second, $first);
      }
      echo("[". $first .",". $second ."] => ". $this->counter ."\n");
    } else {
      echo("\nEmpty BST\n");
    }
  }
}
function main() {
  $obj = new BinarySearchTree();
  /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


  */  
  $obj->add(6);
  $obj->add(3);
  $obj->add(9);
  $obj->add(1);
  $obj->add(5);
  $obj->add(7);
  $obj->add(11);
  $obj->add(-3);
  $obj->add(2);
  $obj->add(12);
  $obj->add(4);
  $obj->counter_nodes(1, 10);
}
main();

Output

[1,10] => 8
/*
 Node Js Program
 Count BST nodes that lie in a given range
*/

class Node {
  
  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {

  constructor() {
    this.root = null;
    this.counter = 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");
    }
  }
  count_element(head, first, second) {
    if (head != null) {
      if (head.data >= first && head.data <= second) {
        this.counter++;
      }
      this.count_element(head.left, first, second);
      this.count_element(head.right, first, second);
    }
  }
  counter_nodes(first, second) {
    if (this.root != null) {
      this.counter = 0;
      if (first < second) {
        this.count_element(this.root, first, second);
      } else {
        this.count_element(this.root, second, first);
      }
      process.stdout.write("[" + first + "," + second + "] => " + this.counter + "\n");
    } else {
      process.stdout.write("\nEmpty BST\n");
    }
  }
}

function main() {
  var obj = new BinarySearchTree();
    /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


   */  
  obj.add(6);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(5);
  obj.add(7);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(12);
  obj.add(4);
  obj.counter_nodes(1, 10);
}

main();

Output

[1,10] => 8
/*
 Swift 4 Program
 Count BST nodes that lie in a given range
*/

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 counter: Int;
  init() {
    self.root = nil;
    self.counter = 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 count_element(_ head: Node? , _ first : Int, _ second: Int) {
    if (head != nil) {
      if (head!.data >= first && head!.data <= second) {
        self.counter += 1;
      }
      self.count_element(head!.left, first, second);
      self.count_element(head!.right, first, second);
    }
  }
  func counter_nodes(_ first: Int, _ second: Int) {
    if (self.root != nil) {
      self.counter = 0;
      if (first < second) {
        self.count_element(self.root, first, second);
      } else {
        self.count_element(self.root, second, first);
      }
      print("[", first ,",", second ,"] => ", self.counter ,"\n");
    } else {
      print("\nEmpty BST\n");
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  /*
              6
            /    \
           /      \
          3        9
         /  \      / \
        1    5    7   11
       / \   /         \
     -3  2  4           12


  */  
  obj.add(6);
  obj.add(3);
  obj.add(9);
  obj.add(1);
  obj.add(5);
  obj.add(7);
  obj.add(11);
  obj.add(-3);
  obj.add(2);
  obj.add(12);
  obj.add(4);
  obj.counter_nodes(1, 10);
}
main();

Output

[1,10] => 8

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