Skip to main content

K’th Largest element in Binary Search Tree

Find the kth largest node in binary tree

Here given code implementation process.

//C Program 
//K’th Largest 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 largest node in binary tree
void find_kth_largest(struct Node*root, int *counter ,struct Node**element ,int k)
{
  if(root!=NULL)
  {

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


    find_kth_largest(root->left,counter,element,k);
    
  }
}
void kth_largest(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_largest(root, &counter, &element, k);

    if(counter < k)
    {
      //If In case given kth Largest node are 
      //Not exist in binary search tree, then
      printf("Given %d Largest node are not exist  \n",  k);
    }
    else
    {
      printf("[%d] largest 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
          \
           8 
  */

  add(&root,7);
  add(&root,4);
  add(&root,3);
  add(&root,5);
  add(&root,9);
  add(&root,8);
  add(&root,10);
  add(&root,8);
  //Test case
 
  kth_largest(root, 6);
  kth_largest(root, 4);
  kth_largest(root, 2);
  kth_largest(root, 5);
  return 0;
}

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
//C++ program
//K’th Largest 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 counter;
  Node *element;
  //Class constructors
  BinarySearchTree() {
    this->counter = 0;
    this->root = NULL;
    this->element = NULL;
  }
  //insert a binary search tree element
  void add(int value) {
    //Create a dynamic node of binary search tree 
    Node *new_node = new Node(value);
    if (new_node != NULL) {
      if (this->root == NULL) {
        //When adds a first node in binary tree
        this->root = new_node;
      } else {
        Node *find = this->root;
        //Add a new node to its proper position
        while (find != NULL) {
          if (find->data >= value) {
            if (find->left == NULL) {
              find->left = new_node;
              return;
            } else {
              //visit left sub-tree
              find = find->left;
            }
          } else {
            if (find->right == NULL) {
              find->right = new_node;
              return;
            } else {
              //visit right sub-tree
              find = find->right;
            }
          }
        }
      }
    } else {
      cout << "Memory Overflow";
    }
  }
  //Find the kth largest node in BST
  void find_kth_largest(Node *head, int k) {
    if (head != NULL) {
      this->find_kth_largest(head->right, k);
      if (this->counter == k) {
        return;
      }
      if (this->element == NULL ||
        (this->element)->data > head->data) {
        //Modified counter variable by one
        (this->counter) ++;
        this->element = head;
      }
      this->find_kth_largest(head->left, k);
    }
  }
  void kth_largest(int k) {
    if (k <= 0) {
      cout << "Invalid node position " << k;
    } else
    if (this->root == NULL) {
      cout << "Empty Binary Search Tree";
    } else {
      this->counter = 0;
      this->element = NULL;
      this->find_kth_largest(this->root, k);
      if (this->counter < k) {
        cout << "Given " << k << " Largest node are not exist " << this->counter<<endl;
      } else {
        cout << "[" << k << "] largest node : " << this->element->data<<endl;
      }
    }
  }
};
int main() {
  BinarySearchTree obj =  BinarySearchTree();
  //Add nodes in binary search tree
  /*
            7
          /   \
         4     9
        / \   / \
       3   5 8   10
              \
               8 
      */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(9);
  obj.add(8);
  obj.add(10);
  obj.add(8);
  //Test case
  obj.kth_largest(6);
  obj.kth_largest(4);
  obj.kth_largest(2);
  obj.kth_largest(5);
  return 0;
}

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
//C# program
//K’th Largest 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 {
  private Node root;
  private int counter;
  private Node element;
  //Class constructors
  BinarySearchTree() {
    counter = 0;
    root = null;
    element = null;
  }
  //insert a binary search tree element
  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 a new node to its proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              return;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              return;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      Console.WriteLine("Memory Overflow");
    }
  }
  //Find the kth largest node in BST
  public void find_kth_largest(Node head, int k) {
    if (head != null) {
      find_kth_largest(head.right, k);
      if (counter == k) {
        return;
      }
      if (element == null ||
        (element).data > head.data) {
        //Modified counter variable by one
        (counter) ++;
        element = head;
      }
      find_kth_largest(head.left, k);
    }
  }
  public void kth_largest(int k) {
    if (k <= 0) {
      Console.WriteLine("Invalid node position " + k);
    } else
    if (root == null) {
      Console.WriteLine("Empty Binary Search Tree");
    } else {
      counter = 0;
      element = null;
      find_kth_largest(root, k);
      if (counter < k) {
        Console.Write("Given " + k + " Largest node are not exist " + counter + "\n");
      } else {
        Console.Write("[" + k + "] largest node : " + element.data + "\n");
      }
    }
  }
  public static void Main(String[] args) {
    BinarySearchTree obj = new BinarySearchTree();
    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(9);
    obj.add(8);
    obj.add(10);
    obj.add(8);
    obj.kth_largest(6);
    obj.kth_largest(4);
    obj.kth_largest(2);
    obj.kth_largest(5);
  }
}

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
<?php
//Php program
//K’th Largest 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 {
  private $root;
  private $counter;
  private $element;
  //Class constructors

  function __construct() {
    $this->counter = 0;
    $this->root = null;
    $this->element = null;
  }
  //insert a binary search tree element

  public  function add($value) {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($value);
    if ($new_node != null) {
      if ($this->root == null) {
        //When adds a first node in binary tree
        $this->root = $new_node;
      } else {
        $find = $this->root;
        //Add a new node to its proper position
        while ($find != null) {
          if ($find->data >= $value) {
            if ($find->left == null) {
              $find->left = $new_node;
              return;
            } else {
              //visit left sub-tree
              $find = $find->left;
            }
          } else {
            if ($find->right == null) {
              $find->right = $new_node;
              return;
            } else {
              //visit right sub-tree
              $find = $find->right;
            }
          }
        }
      }
    } else {
      echo("Memory Overflow");
    }
  }
  //Find the kth largest node in BST
  public  function find_kth_largest($head, $k) {
    if ($head != null) {
      $this->find_kth_largest($head->right, $k);
      if ($this->counter == $k) {
        return;
      }
      if ($this->element == null ||
        $this->element->data > $head->data) {
        //Modified counter variable by one
        $this->counter ++;
        $this->element = $head;
      }
      $this->find_kth_largest($head->left, $k);
    }
  }
  public  function kth_largest($k) {
    if ($k <= 0) {
      //When  given k is not valid positive values

      echo("Invalid node position ". $k);
    } else
    if ($this->root == null) {
      //When Binary Search Tree are no elements

      echo("Empty Binary Search Tree");
    } else {
      $this->counter = 0;
      $this->element = null;
      $this->find_kth_largest($this->root, $k);
      if ($this->counter < $k) {
        //If In case given kth Largest node are 
        //Not exist in binary search tree, then

        echo("Given ". $k ." Largest node are not exist ". $this->counter ."\n");
      } else {
        echo("[". $k ."] largest node : ". $this->element->data ."\n");
      }
    }
  }
}

function main() {
  $obj = new BinarySearchTree();
  //Add nodes in binary search tree
  /*
            7
          /   \
         4     9
        / \   / \
       3   5 8   10
              \
               8 
      */
  $obj->add(7);
  $obj->add(4);
  $obj->add(3);
  $obj->add(5);
  $obj->add(9);
  $obj->add(8);
  $obj->add(10);
  $obj->add(8);
  //Test case
  $obj->kth_largest(6);
  $obj->kth_largest(4);
  $obj->kth_largest(2);
  $obj->kth_largest(5);

}
main();

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
//Node Js program
//K’th Largest element in Binary Search Tree
class Node {
  constructor(value) {
    this.data = value;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  //Class constructors

  constructor() {
    this.counter = 0;
    this.root = null;
    this.element = null;
  }

  //insert a binary search tree element
  add(value) {
    //Create a dynamic node of binary search tree 
    var new_node = new Node(value);
    if (new_node != null) {
      if (this.root == null) {
        //When adds a first node in binary tree
        this.root = new_node;
      } else {
        var find = this.root;
        //Add a new node to its proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;
              return;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;
              return;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      process.stdout.write("Memory Overflow");
    }
  }

  //Find the kth largest node in BST
  find_kth_largest(head, k) {
    if (head != null) {
      this.find_kth_largest(head.right, k);
      if (this.counter == k) {
        return;
      }

      if (this.element == null ||
        (this.element).data > head.data) {
        //Modified counter variable by one
        (this.counter) ++;
        this.element = head;
      }
      this.find_kth_largest(head.left, k);
    }
  }
  kth_largest(k) {
    if (k <= 0) {
      //When  given k is not valid positive values

      process.stdout.write("Invalid node position " + k);
    } else
    if (this.root == null) {
      //When Binary Search Tree are no elements

      process.stdout.write("Empty Binary Search Tree");
    } else {
      this.counter = 0;
      this.element = null;
      this.find_kth_largest(this.root, k);
      if (this.counter < k) {
        //If In case given kth Largest node are 
        //Not exist in binary search tree, then

        process.stdout.write("Given " + k + " Largest node are not exist " + this.counter + "\n");
      } else {
        process.stdout.write("[" + k + "] largest node : " + this.element.data + "\n");
      }
    }
  }
}

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

main();

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
# Python 3 program
# K’th Largest element in Binary Search Tree
class Node :
  
  def __init__(self, value) :
    self.data = value
    self.left = None
    self.right = None
  

class BinarySearchTree :
  
  # Class constructors
  def __init__(self) :
    self.counter = 0
    self.root = None
    self.element = None
  
  # insert a binary search tree element
  def add(self, value) :
    # Create a dynamic node of binary search tree 
    new_node = Node(value)
    if (new_node != None) :
      if (self.root == None) :
        # When adds a first node in binary tree
        self.root = new_node
      else :
        find = self.root
        # Add a new node to its proper position
        while (find != None) :
          if (find.data >= value) :
            if (find.left == None) :
              find.left = new_node
              return
            else :
              # visit left sub-tree
              find = find.left
            
          else :
            if (find.right == None) :
              find.right = new_node
              return
            else :
              # visit right sub-tree
              find = find.right
            
          
        
      
    else :
      print("Memory Overflow", end = "")
    
  
  # Find the kth largest node in BST
  def find_kth_largest(self, head, k) :
    if (head != None) :
      self.find_kth_largest(head.right, k)
      if (self.counter == k) :
        return
      
      if (self.element == None or(self.element).data > head.data) :
        # Modified counter variable by one
        self.counter += 1
        self.element = head
      
      self.find_kth_largest(head.left, k)
    
  
  def kth_largest(self, k) :
    if (k <= 0) :
      
        # When  given k is not valid positive values
      print("Invalid node position ", k, end = "")
    elif (self.root == None) :
      
      # When Binary Search Tree are no elements
      print("Empty Binary Search Tree", end = "")
    else :
      self.counter = 0
      self.element = None
      self.find_kth_largest(self.root, k)
      if (self.counter < k) :
        
        # If In case given kth Largest node are 
        # Not exist in binary search tree, then
        print("Given ", k ," Largest node are not exist ", self.counter )
      else :
        print("[", k ,"] largest node : ", self.element.data)
      
    
  

def main() :
  obj = BinarySearchTree()
  # Add nodes in binary search tree
  # 
  #           7
  #         /   \
  #        4     9
  #       / \   / \
  #      3   5 8   10
  #             \
  #              8 
  #     
  
  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(9)
  obj.add(8)
  obj.add(10)
  obj.add(8)
  # Test case
  obj.kth_largest(6)
  obj.kth_largest(4)
  obj.kth_largest(2)
  obj.kth_largest(5)


if __name__ == "__main__":
  main()

Output

[ 6 ] largest node :  4
[ 4 ] largest node :  7
[ 2 ] largest node :  9
[ 5 ] largest node :  5
# Ruby program
# K’th Largest element in Binary Search Tree
class Node
    # Define the accessor and reader of 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
    # Define the accessor and reader of class BinarySearchTree
    attr_reader :root, :counter, :element
    attr_accessor :root, :counter, :element 
  
  # Class constructors

  def initialize() 
    @counter = 0
    @root = nil
    @element = nil
  end
  # insert a binary search tree element
  def add(value) 
    # Create a dynamic node of binary search tree 
    new_node = Node.new(value)
    if (new_node != nil) 
      if (@root == nil) 
        # When adds a first node in binary tree
        @root = new_node
      else 
        find = @root
        # Add a new node to its proper position
        while (find != nil) 
          if (find.data >= value) 
            if (find.left == nil) 
              find.left = new_node
              return
            else 
              # visit left sub-tree
              find = find.left
            end
          else 
            if (find.right == nil) 
              find.right = new_node
              return
            else 
              # visit right sub-tree
              find = find.right
            end
          end
        end
      end
    else 
      print("Memory Overflow")
    end
  end
  # Find the kth largest node in BST
  def find_kth_largest(head, k) 
    if (head != nil) 
      self.find_kth_largest(head.right, k)
      if (@counter == k) 
        return
      end
      if (@element == nil ||
        (@element).data > head.data) 
        # Modified counter variable by one
        @counter += 1
        @element = head
      end
      self.find_kth_largest(head.left, k)
    end
  end
  def kth_largest(k) 
    if (k <= 0) 
      # When  given k is not valid positive values
      print("Invalid node position ", k)
    elsif (@root == nil) 
      # When Binary Search Tree are no elements
      print("Empty Binary Search Tree")
    else 
      @counter = 0
      @element = nil
      self.find_kth_largest(@root, k)
      if (@counter < k) 
        # If In case given kth Largest node are 
        # Not exist in binary search tree, then
        print("Given ", k ," Largest node are not exist ", @counter ,"\n")
      else 
        print("[", k ,"] largest node  : ", @element.data ,"\n")
      end
    end
  end
end
def main() 
  obj = BinarySearchTree.new()
  # Add nodes in binary search tree
  # 
  #           7
  #         /   \
  #        4     9
  #       / \   / \
  #      3   5 8   10
  #             \
  #              8 
  #     
  
  obj.add(7)
  obj.add(4)
  obj.add(3)
  obj.add(5)
  obj.add(9)
  obj.add(8)
  obj.add(10)
  obj.add(8)
  # Test case
  obj.kth_largest(6)
  obj.kth_largest(4)
  obj.kth_largest(2)
  obj.kth_largest(5)
end
main()

Output

[6] largest node  : 4
[4] largest node  : 7
[2] largest node  : 9
[5] largest node  : 5

//Scala program
//K’th Largest element in Binary Search Tree
class Node(var data: Int,
  var left: Node,
    var right: Node) {

  def this(value: Int) {
    this(value,null,null);
  }
}
class BinarySearchTree(var root: Node,
  var counter: Int,
    var element: Node) {

  //Class constructors
  def this() {
    this(null,0,null);
  }
  //insert a binary search tree element
  def add(value: Int): Unit = {
    //Create a dynamic node of binary search tree 
    var new_node: Node = new Node(value);

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

        //Add a new node to its proper position
        while (find != null) {
          if (find.data >= value) {
            if (find.left == null) {
              find.left = new_node;

              return;
            } else {
              //visit left sub-tree
              find = find.left;
            }
          } else {
            if (find.right == null) {
              find.right = new_node;

              return;
            } else {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    } else {
      print("Memory Overflow");
    }
  }
  //Find the kth largest node in BST
  def find_kth_largest(head: Node, k: Int): Unit = {
    if (head != null) {
      find_kth_largest(head.right, k);

      if (counter == k) {
        return;
      }
      if (element == null ||
        (element).data > head.data) {
        //Modified counter variable by one
        (counter) += 1;
        element = head;
      }
      find_kth_largest(head.left, k);
    }
  }
  def kth_largest(k: Int): Unit = {
    if (k <= 0) {
      //When  given k is not valid positive values

      print("Invalid node position " + k);
    } else
    if (root == null) {
      //When Binary Search Tree are no elements

      print("Empty Binary Search Tree");
    } else {
      counter = 0;
      element = null;
      find_kth_largest(root, k);

      if (counter < k) {
        //If In case given kth Largest node are 
        //Not exist in binary search tree, then
        print("Given " + k + " Largest node are not exist " + counter + "\n");
      } else {
        print("[" + k + "] largest node : " + element.data + "\n");
      }
    }
  }
}
object Main {
  def main(args: Array[String]): Unit = {
    var obj: BinarySearchTree = new BinarySearchTree();

    //Add nodes in binary search tree
    /*
              7
            /   \
           4     9
          / \   / \
         3   5 8   10
                \
                 8 
        */
    obj.add(7);
    obj.add(4);
    obj.add(3);
    obj.add(5);
    obj.add(9);
    obj.add(8);
    obj.add(10);
    obj.add(8);

    //Test case
    obj.kth_largest(6);
    obj.kth_largest(4);
    obj.kth_largest(2);
    obj.kth_largest(5);
  }
}

Output

[6] largest node : 4
[4] largest node : 7
[2] largest node : 9
[5] largest node : 5
//Swift program
//K’th Largest 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? ;
  //Class constructors
  init() {
    self.counter = 0;
    self.root = nil;
    self.element = nil;
  }
  //insert a binary search tree element
  func add(_ value: Int) {
    //Create a dynamic node of binary search tree 
    let new_node: Node? = Node(value);
    if (new_node != nil) {
      if (self.root == nil) {
        //When adds a first node in binary tree
        self.root = new_node;
      } else {
        var find: Node? = self.root;
        //Add a new node to its proper position
        while (find != nil) {
          if (find!.data >= value) {
            if (find!.left == nil) {
              find!.left = new_node;
              return;
            } else {
              //visit left sub-tree
              find = find!.left;
            }
          } else {
            if (find!.right == nil) {
              find!.right = new_node;
              return;
            } else {
              //visit right sub-tree
              find = find!.right;
            }
          }
        }
      }
    } else {
      print("Memory Overflow", terminator: "");
    }
  }
  //Find the kth largest node in BST
  func find_kth_largest(_ head: Node? , _ k : Int) {
    if (head != nil) {
      self.find_kth_largest(head!.right, k);
      if (self.counter == k) {
        return;
      }
      if (self.element == nil ||
        self.element!.data > head!.data) {
        //Modified counter variable by one
        (self.counter) += 1;
        self.element = head;
      }
      self.find_kth_largest(head!.left, k);
    }
  }
  func kth_largest(_ k: Int) {
    if (k <= 0) {
      
      //When  given k is not valid positive values
      print("Invalid node position ", k, terminator: "");
    } else
    if (self.root == nil) {
      
      //When Binary Search Tree are no elements
      print("Empty Binary Search Tree", terminator: "");
    } else {
      self.counter = 0;
      self.element = nil;
      self.find_kth_largest(self.root, k);
      if (self.counter < k) {
        
        //If In case given kth Largest node are 
        //Not exist in binary search tree, then
        print("Given ", k ," Largest node are not exist ", self.counter ,"\n", terminator: "");
      } else {
        print("[", k ,"] largest node : ", self.element!.data ,"\n", terminator: "");
      }
    }
  }
}
func main() {
  let obj: BinarySearchTree = BinarySearchTree();
  //Add nodes in binary search tree
  /*
            7
          /   \
         4     9
        / \   / \
       3   5 8   10
              \
               8 
      */
  obj.add(7);
  obj.add(4);
  obj.add(3);
  obj.add(5);
  obj.add(9);
  obj.add(8);
  obj.add(10);
  obj.add(8);
  //Test case
  obj.kth_largest(6);
  obj.kth_largest(4);
  obj.kth_largest(2);
  obj.kth_largest(5);
}
main();

Output

[ 6 ] largest node :  4
[ 4 ] largest node :  7
[ 2 ] largest node :  9
[ 5 ] largest node :  5
//Java program
//K’th Largest 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
{
  private Node root;
  private int counter;
  private Node element;
  //Class constructors
  BinarySearchTree()
  {
    counter=0;
    root=null;
    element=null;
  } 

  //insert a binary search tree element
  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 a new node to its proper position
        while(find != null)
        {
          if(find.data >= value)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              return;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              return;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }
  //Find the kth largest node in BST
  public void find_kth_largest( Node head ,int k)
  {
    
    if(head!=null)
    {

      find_kth_largest(head.right,k);
      if( counter == k)
      {
        return;
      }
      if( element==null || ( element).data > head.data)
      {
        //Modified counter variable by one
        ( counter)++;
         element=head;
        
      }


      find_kth_largest(head.left,k);
      
    }
    
  }

  public void kth_largest(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 Binary Search Tree are no elements
      System.out.println("Empty Binary Search Tree");
    }
    else
    {


      counter = 0;
      
      element=null;

      find_kth_largest(root,k);

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

  public static void main(String[] args) 
  {

    BinarySearchTree obj = new BinarySearchTree();

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

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

    //Test case

    obj.kth_largest(6);
    obj.kth_largest(4);
    obj.kth_largest(2);
    obj.kth_largest(5);

  }
}

Output

[ 6 ] largest node :  4
[ 4 ] largest node :  7
[ 2 ] largest node :  9
[ 5 ] largest node :  5
Last updated on by Kalkicode




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