Find Kth largest element in Binary Search Tree.
Lets understand the problem statement correctly, What is the Input and the expected output.
Simple approach
STEP 1. Take a variable counter, which keep track of number of largest element read till now.
STEP 2. Do In-order traversal starting from right side (Right to Left instead of Left to Right),
instead of printing the node in in-order traversal, increment the counter till it matches K. STEP 3. Check whether counter value is equal to K.
STEP 4. If YES, then current node is Kth largest node and return it.
If NO, then return -1 as indication that given 'K' is invalid.
Java Program to find Kth largest element in BST using First Approach.
package javabypatel.tree;
public class FindKLargestElementInBinarySearchTree {
private Node rootNode;
private static int counter;
public static void main(String[] args) {
new FindKLargestElementInBinarySearchTree();
}
public FindKLargestElementInBinarySearchTree() {
addNode(rootNode, 40);
addNode(rootNode, 20);
addNode(rootNode, 60);
addNode(rootNode, 10);
addNode(rootNode, 30);
addNode(rootNode, 50);
addNode(rootNode, 70);
printTreeInOrder(rootNode);
System.out.println();
Node kthLargestNode = findKthLargestItem(rootNode, 5);
if(kthLargestNode!=null){
System.out.println("Kth Largest Node is :"+kthLargestNode.getData());
}else{
System.out.println("Kth Largest Node not found");
}
}
private Node findKthLargestItem(Node rootNode, int k) {
if(rootNode==null){
return null;
}
//Instead of Left to Right, we will traverse in Right to Left fashion because largest element
//are present of Right side of Root Node.
Node node = findKthLargestItem(rootNode.getRight(), k);
//If counter is not equal to K, then only increment the counter.
//Once counter is equal to K, it means we have found the desired largest element and no need to increment further,
//Take the back up of the current node as it might be the Kth largest element we are looking for.
if(counter != k){
counter++;
node = rootNode;
}
//This is the place where actual check is going to happen between counter and K,
//If counter matched K, it means we found the node and no need to find further so simply return the found node.
if(counter == k){
return node;
}else{
return findKthLargestItem(rootNode.getLeft(), k);
}
}
private void printTreeInOrder(Node rootNode){
if(rootNode==null)
return;
printTreeInOrder(rootNode.getLeft());
System.out.print(rootNode.getData() + " ");
printTreeInOrder(rootNode.getRight());
}
private void addNode(Node rootNode, int data){
if(rootNode==null){
Node temp1 = new Node(data);
this.rootNode=temp1;
}else{
addNodeInProperPlace(rootNode, data);
}
}
private void addNodeInProperPlace(Node rootNode, int data){
if(data>rootNode.getData()){
if(rootNode.getRight()!=null){
addNode(rootNode.getRight(), data);
}else{
Node temp1 = new Node(data);
rootNode.setRight(temp1);
}
}else if(data<rootNode.getData()){
if(rootNode.getLeft()!=null){
addNode(rootNode.getLeft(), data);
}else{
Node temp1 = new Node(data);
rootNode.setLeft(temp1);
}
}
}
}
Node.java
package javabypatel.tree;
public class Node{
private Node left;
private Node right;
private int data;
public Node(int data){
this.data=data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
Another approach of Finding K'th largest item in BST
In this approach, we will use the Binary Search Tree property that,
1. Left sub tree of a Node contains elements smaller than Node.
2. Right sub tree of a Node contains elements larger than Node.
So, If we want to find Kth largest element, we need to look at right side of a Root Node first,
If Kth largest is not found on right side then only we will explore left side of Root Node.
Algorithm
STEP 1: Identify the children's of Right sub tree of Root Node. (store it in variable childCount).
STEP 2: If (childCount == K), we found the element.
STEP 3: If (childCount > K), then K is present some where in Right subtree of Root Node and
we will explore right subtree of Root Node by moving one step towards Right of it.
(rootNode -> right) and repeat the process.
STEP 4: If (childCount < K), then K is not present in Right subtree of Root Node and we will
explore left subtree of Root Node by moving one step towards left of it.
(rootNode -> left) and repeat the process.
While moving towards Left, we have to keep in mind that we already traversed
(childCount) largest element in BST and now we need to find (K - childCount) node in
left sub tree
Repeat steps until node is not found.
Look at the below picture for better understanding of it.
Java Program to find Kth largest element in BST using Second Approach.
package javabypatel.tree;
public class FindKLargestElementInBinarySearchTree {
private Node rootNode;
private static int counter;
public static void main(String[] args) {
new FindKLargestElementInBinarySearchTree();
}
public FindKLargestElementInBinarySearchTree() {
addNode(rootNode, 40);
addNode(rootNode, 20);
addNode(rootNode, 60);
addNode(rootNode, 10);
addNode(rootNode, 30);
addNode(rootNode, 50);
addNode(rootNode, 70);
printTreeInOrder(rootNode);
System.out.println();
int kthLargestNode = findKthLargestItem(rootNode, 7);
if(kthLargestNode==-1){
System.out.println("Kth largest element not found.");
}else{
System.out.println("Kth largest element is :"+kthLargestNode);
}
}
private int findKthLargestItem(Node rootNode, int k) {
if(rootNode==null){
return -1;
}
int childCount = getNodeCount(rootNode.getRight());
if(childCount+1==k){
return rootNode.getData();
}else if(childCount+1>=k){
return findKthLargestItem(rootNode.getRight(), k);
}else{
return findKthLargestItem(rootNode.getLeft(), k - (childCount+1));
}
}
private int getNodeCount(Node node){
if(node == null){
return 0;
}
int left = getNodeCount(node.getLeft());
int right = getNodeCount(node.getRight());
return 1 + left + right;
}
private void printTreeInOrder(Node rootNode){
if(rootNode==null)
return;
printTreeInOrder(rootNode.getLeft());
System.out.print(rootNode.getData() + " ");
printTreeInOrder(rootNode.getRight());
}
private void addNode(Node rootNode, int data){
if(rootNode==null){
Node temp1 = new Node(data);
this.rootNode=temp1;
}else{
addNodeInProperPlace(rootNode, data);
}
}
private void addNodeInProperPlace(Node rootNode, int data){
if(data>rootNode.getData()){
if(rootNode.getRight()!=null){
addNode(rootNode.getRight(), data);
}else{
Node temp1 = new Node(data);
rootNode.setRight(temp1);
}
}else if(data<rootNode.getData()){
if(rootNode.getLeft()!=null){
addNode(rootNode.getLeft(), data);
}else{
Node temp1 = new Node(data);
rootNode.setLeft(temp1);
}
}
}
}
You may also like to see
Find Kth SMALLEST element in BST(Binary Search Tree)
Check whether Binary Tree is foldable or not.
Check if two nodes are cousins in a Binary Tree.
Get Level/Height of node in binary tree
Print nodes at K distance from Leaf node in Binary tree.
Construct a Binary Tree from In-order and Post-order traversals.
Print Nodes in Top View of Binary Tree.
Zig Zag Traversal of Binary Tree.
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment