K’th smallest element in Binary Search Tree

Find the kth smallest node in binary tree

Here given code implementation process.

//C Program 
//K’th smallest 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
  }

}

//Find the kth smallest node in binary tree
void find_kth_smallest(struct Node*root, int *counter ,struct Node**element ,int k)
{
  if(root!=NULL)
  {

    find_kth_smallest(root->left,counter,element,k);

    if(*counter == k)
    {
      return;
    }
    if(*element==NULL || (*element)->data < root->data)
    {
      //Modified counter variable by one
      (*counter)++;
      *element=root;
      
    }

    find_kth_smallest(root->right,counter,element,k);
    
  }
}
void kth_smallest(struct Node*root,int k)
{
  if(k <= 0)
  {
    //When  given k is not valid positive values
    printf("Invalid node position %d\n",k);
  }
  else if(root == NULL)
  {
    //When BST are no have elements
    printf("Empty Binary Search Tree\n");
  }
  else
  {

    int counter = 0;
    struct Node*element=NULL;
    find_kth_smallest(root, &counter, &element, k);

    if(counter < k)
    {
      //If In case given kth smallest node are 
      //Not exist in binary search tree, then
      printf("Given %d smallest node are not exist  \n",  k);
    }
    else
    {
      printf("[%d] smallest node : %d \n",k,element->data );
    }
  }
  

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

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

  add(&root,7);
  add(&root,4);
  add(&root,3);
  add(&root,5);
  add(&root,9);
  add(&root,8);
  add(&root,10);
  add(&root,4);
  //Test case
 
  kth_smallest(root, 6);
  kth_smallest(root, 4);

  return 0;
}

Output

[6] smallest node : 9 
[4] smallest node : 7 
//C++ Program 
//K’th smallest element in Binary Search Tree
#include <iostream>
using namespace std;
//structure of Binary Search Tree node
struct Node

{
  int data;
  struct Node *left,*right; 
};
class BST
{
  Node*root;
public:

  BST();
  //public methods
  void add(int);
  void find_kth_smallest( Node*, int * , Node** ,int );
  void kth_smallest(int);

};
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");
  }
}
//Find the kth smallest node in bst
void BST:: find_kth_smallest( Node*root, int *counter , Node**element ,int k)
{
  if(root!=NULL)
  {

    find_kth_smallest(root->left,counter,element,k);

    if(*counter == k)
    {
      return;
    }
    if(*element==NULL || (*element)->data < root->data)
    {
      //Modified counter variable by one
      (*counter)++;
      *element=root;
      
    }

    find_kth_smallest(root->right,counter,element,k);
  }
}

void BST:: kth_smallest(int k)
{
  if(k <= 0)
  {
    //When  given k is not valid positive values
    cout<<"Invalid node position "<< k<<endl;
  }
  else if(root == NULL)
  {
    //When BST are no have elements
    cout<<"Empty Binary Search Tree"<<endl;
  }
  else
  {

    int counter = 0;
    Node*element=NULL;
    find_kth_smallest(root, &counter, &element, k);

    if(counter < k)
    {
      //If In case given kth smallest node are 
      //Not exist in binary search tree, then
      cout<<"Given "<< k <<" smallest node are not exist "<<endl;
    }
    else
    {
      cout<<"["<< k <<"] smallest node : "<< element->data<<endl;
    }
  }
}
int main()
{

  BST obj;

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

  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(9);
  obj.add(8);
  obj.add(10);
  obj.add(4);

  //Test case
 
  obj.kth_smallest(6);
  obj.kth_smallest(4);


  return 0;
}

Output

[6] smallest node : 9
[4] smallest node : 7
//Java program
//K’th smallest element in Binary Search Tree
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  private int counter;
  private Node element;
  //Class constructors
  BST()
  {
    counter=0;
    root=null;
    element=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");
    }
  }
  //Find the kth smallest node in bst
  public void find_kth_smallest( Node root ,int k)
  {
    
    if(root!=null)
    {
      find_kth_smallest(root.left,k);
      
      if( counter == k)
      {
        return;
      }
      if( element==null || element.data < root.data)
      {
        //Modified counter variable by one
        counter++;
        element=root;
        
      }

      find_kth_smallest(root.right,k);
      
    }
    
  }

  public void kth_smallest(int k)
  {
    if(k <= 0)
    {
    //When  given k is not valid positive values
      System.out.println("Invalid node position "+ k);
    }
    else if(root == null)
    {
    //When BST are no have elements
      System.out.println("Empty Binary Search Tree");
    }
    else
    {


      counter = 0;

      element=null;

      find_kth_smallest(root,k);

      if(counter < k)
      {
        //If In case given kth smallest node are 
        //Not exist in binary search tree, then
        System.out.println("Given "+ k +" smallest node are not exist "+counter);
      }
      else
      {
        System.out.println("["+ k +"] smallest node : "+ element.data);
      }
     
    }
  }

  public static void main(String[] args) 
  {

    BST obj = new BST();

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

    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(9);
    obj.add(8);
    obj.add(10);
    obj.add(4);

    //Test case

    obj.kth_smallest(6);
    obj.kth_smallest(4);


    }
}

Output

[6] smallest node : 9
[4] smallest node : 7
#Python Program 
#K’th smallest element in Binary Search Tree
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
    self.element=None
    self.counter=0
  
  #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
    
  #Find the kth smallest node in bst
  def find_kth_smallest(self,root,k):
    
    if(root!=None):

      
      self.find_kth_smallest(root.left,k)
      if(self.counter == k):
        return
      
      if( self.element==None  or self.element.data < root.data):
        #Modified counter variable by one
        self.counter+=1
        self.element=root

      self.find_kth_smallest(root.right,k)
      

  def kth_smallest(self,k) :

    if(k <= 0):

      #When  given k is not valid positive values
      print("Invalid node position ", k)
    
    elif(self.root == None):

      #When BST are no have elements
      print("Empty Binary Search Tree")
    
    else:


      self.counter = 0

      self.element=None

      self.find_kth_smallest(self.root,k)

      if(self.counter < k):
        #If In case given kth smallest node are 
        #Not exist in binary search tree then
        print("Given ", k ," smallest node are not exist ")
      
      else :
        print("[", k ,"] smallest node : ", self.element.data)
      

def main():

  obj = BST()


  #Add nodes in binary search tree
  #
  #        7
  #      /   \
  #     4     9
  #    / \   / \
  #   3   5 8   10
  #      /    
  #     4     
  #

  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(9)
  obj.add(8)
  obj.add(10)
  obj.add(4)

  #Test case
 
  obj.kth_smallest(6)
  obj.kth_smallest(4)


if __name__ =="__main__":
  main()

Output

[ 6 ] smallest node :  9
[ 4 ] smallest node :  7
//C# program
//K’th smallest element in Binary Search Tree
using System;
public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{
  public Node root;
  private int counter;
  private Node element;
  //Class constructors
  BST()
  {
    counter=0;
    root=null;
    element=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");
    }
  }
  //Find the kth smallest node in bst
  public void find_kth_smallest( Node root ,int k)
  {

    if(root!=null)
    {
      find_kth_smallest(root.left,k);

      if( counter == k)
      {
        return;
      }
      if( element==null || element.data < root.data)
      {
        //Modified counter variable by one
        counter++;
        element=root;

      }

      find_kth_smallest(root.right,k);

    }

  }

  public void kth_smallest(int k)
  {
    if(k <= 0)
    {
      //When  given k is not valid positive values
      Console.WriteLine("Invalid node position "+ k);
    }
    else if(root == null)
    {
      //When BST are no have elements
      Console.WriteLine("Empty Binary Search Tree");
    }
    else
    {


      counter = 0;

      element=null;

      find_kth_smallest(root,k);

      if(counter < k)
      {
        //If In case given kth smallest node are 
        //Not exist in binary search tree, then
        Console.WriteLine("Given "+ k +" smallest node are not exist "+counter);
      }
      else
      {
        Console.WriteLine("["+ k +"] smallest node : "+ element.data);
      }

    }
  }

  public static void Main(String[] args) 
  {

    BST obj = new BST();

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

    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(9);
    obj.add(8);
    obj.add(10);
    obj.add(4);

    //Test case

    obj.kth_smallest(6);
    obj.kth_smallest(4);


  }
}

Output

[6] smallest node : 9
[4] smallest node : 7
<?php
//Php program 
//K’th smallest element in Binary Search Tree
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
  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;
          }
        }
      }
    }

  }
//Find the kth smallest node in bst
function find_kth_smallest($root, &$counter ,&$element ,$k)
{
  if($root!=NULL)
  {

    
    $this->find_kth_smallest($root->left,$counter,$element,$k);

    if($counter == $k)
    {
      return;
    }
    if($element==NULL || $element->data < $root->data)
    {
      //Modified counter variable by one
      $counter++;
      $element=$root;
      
    }
    $this->find_kth_smallest($root->right,$counter,$element,$k);

    
    
  }
}

function kth_smallest($k)
{
  if($k <= 0)
  {
    //When  given k is not valid positive values
    echo "Invalid node position ".$k;
  }
  else if($this->root == NULL)
  {
    //When BST are no have elements
    echo "Empty Binary Search Tree\n";
  }
  else
  {

    $counter = 0;
    $element = NULL;
    $this->find_kth_smallest($this->root, $counter, $element, $k);

    if($counter < $k)
    {
      //If In case given kth smallest node are 
      //Not exist in binary search tree; then
      echo "Given $k smallest node are not exist \n";
    }
    else
    {
      echo "[$k] smallest node : $element->data \n";
    }
  }
}

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

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

  $obj->add(7);
  $obj->add(4);
  $obj->add(3);
  $obj->add(5);
  $obj->add(9);
  $obj->add(8);
  $obj->add(10);
  $obj->add(4);

  //Test case
 
  $obj->kth_smallest(6);
  $obj->kth_smallest(4);

}
   main();
?>

Output

[6] smallest node : 9 
[4] smallest node : 7 
# Ruby Program
# K’th smallest 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, :counter, :element
  attr_accessor :root, :counter, :element
  def initialize() 
    @counter = 0
    @root = nil
    @element = nil
  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_kth_smallest(head, k) 
    if (head != nil) 
      self.find_kth_smallest(head.left, k)
      if (@counter == k) 
        return
      end
      if (@element == nil or @element.data < head.data) 
        @counter += 1
        @element = head
      end
      self.find_kth_smallest(head.right, k)
    end
  end
  def kth_smallest(k) 
    if (k <= 0) 
      print("\nInvalid node position ", k)
    elsif (@root == nil) 
      print("\nEmpty Binary Search Tree")
    else 
      @counter = 0
      @element = nil
      self.find_kth_smallest(@root, k)
      if (@counter < k) 
        print("\nGiven ", k ," smallest node are not exist ", @counter)
      else 
        print("\n[", k ,"] smallest node  :", @element.data)
      end
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  #Add nodes in binary search tree
  #
  #        7
  #      /   \
  #     4     9
  #    / \   / \
  #   3   5 8   10
  #      /    
  #     4     
  #
  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(9)
  obj.add(8)
  obj.add(10)
  obj.add(4)
  obj.kth_smallest(6)
  obj.kth_smallest(4)
end


main()

Output

[6] smallest node  :9
[4] smallest node  :7
/*
 Node Js Program
 K’th smallest element in Binary Search Tree
*/

class Node {

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

  constructor() {
    this.counter = 0;
    this.root = null;
    this.element = null;
  }
  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_kth_smallest(head, k) {
    if (head != null) {
      this.find_kth_smallest(head.left, k);
      if (this.counter == k) {
        return;
      }
      if (this.element == null || this.element.data < head.data) {
        this.counter++;
        this.element = head;
      }
      this.find_kth_smallest(head.right, k);
    }
  }
  kth_smallest(k) {
    if (k <= 0) {
      process.stdout.write("\nInvalid node position " + k);
    } else
    if (this.root == null) {
      process.stdout.write("\nEmpty Binary Search Tree");
    } else {
      this.counter = 0;
      this.element = null;
      this.find_kth_smallest(this.root, k);
      if (this.counter < k) {
        process.stdout.write("\nGiven " + k + " smallest node are not exist " + this.counter);
      } else {
        process.stdout.write("\n[" + k + "] smallest node : " + this.element.data);
      }
    }
  }
}

function main() {
  var obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /*
        7
      /   \
     4     9
    / \   / \
   3   5 8   10
      /    
     4     
  */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(9);
  obj.add(8);
  obj.add(10);
  obj.add(4);
  obj.kth_smallest(6);
  obj.kth_smallest(4);
}

main();

Output

[6] smallest node  :9
[4] smallest node  :7
/*
 Swift 4 Program
 K’th smallest 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 counter: Int;
  var element: Node? ;
  init() {
    self.counter = 0;
    self.root = nil;
    self.element = nil;
  }
  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_kth_smallest(_ head: Node? , _ k : Int) {
    if (head != nil) {
      self.find_kth_smallest(head!.left, k);
      if (self.counter == k) {
        return;
      }
      if (self.element == nil || self.element!.data < head!.data) {
        self.counter += 1;
        self.element = head;
      }
      self.find_kth_smallest(head!.right, k);
    }
  }
  func kth_smallest(_ k: Int) {
    if (k <= 0) {
      print("\nInvalid node position ", k);
    } else
    if (self.root == nil) {
      print("\nEmpty Binary Search Tree");
    } else {
      self.counter = 0;
      self.element = nil;
      self.find_kth_smallest(self.root, k);
      if (self.counter < k) {
        print("Given ", k ," smallest node are not exist ", self.counter);
      } else {
        print("[", k ,"] smallest node : ", self.element!.data);
      }
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /*
          7
        /   \
       4     9
      / \   / \
     3   5 8   10
        /    
       4     
  */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(9);
  obj.add(8);
  obj.add(10);
  obj.add(4);
  obj.kth_smallest(6);
  obj.kth_smallest(4);
}
main();

Output

[6] smallest node  :9
[4] smallest node  :7


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