Find Kth smallest 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 smallest element read till now.
STEP 2. Do In order traversal, 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 smallest node and return it.
If NO, then return -1 as indication that given 'K' is invalid.
Java Program to find Kth smallest element in BST using First Approach.
package javabypatel.tree;
public class FindKSmallestElementInBinarySearchTree {
private Node rootNode;
private static int counter;
public static void main(String[] args) {
new FindKSmallestElementInBinarySearchTree();
}
public FindKSmallestElementInBinarySearchTree() {
addNode(rootNode, 40);
addNode(rootNode, 20);
addNode(rootNode, 60);
addNode(rootNode, 10);
addNode(rootNode, 30);
addNode(rootNode, 50);
addNode(rootNode, 70);
printTreeInOrder(rootNode);
Node kthSmallestNode = findKthSmallestItem(rootNode, 4);
if(kthSmallestNode!=null){
System.out.println("\nElement is :"+kthSmallestNode.getData());
}else{
System.out.println("\nElement not found");
}
}
private Node findKthSmallestItem(Node rootNode, int k) {
if(rootNode == null){
return null;
}
Node node = findKthSmallestItem(rootNode.getLeft(), k);
//This means we found the node on the left side and no need to go check right side.
if (node != null) {
return node;
}
//we visited left node, so increment our counter.
counter++;
//once counter is equal to K, it means we have found the desired smallest element.
if (counter == k) {
return rootNode;
}
//we didn't found our element yet
return findKthSmallestItem(rootNode.getRight(), 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 without using the static variable.
public static Node nthSmallestElement(Node root, int n) {
return nthSmallestElementHelper(root, new int[] {n});
}
public static Node nthSmallestElementHelper(Node root, int[] n) {
if (root == null) {
return null;
}
Node lnode = nthSmallestElementHelper(root.getLeft(), n);
if (lnode != null) {
return lnode;
}
n[0]--;
if (n[0] == 0) {
return root;
}
return nthSmallestElementHelper(root.getRight(), n);
}
Another approach of Finding K'th smallest 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 higher than Node.
So, If we want to find Kth lowest element, we need to look at Left side of a Root Node first,
If Kth smallest is not found on Left side then only we will explore right side of Root Node.
Algorithm
STEP 1: Identify the children's of Left 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 Left 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.
STEP 4: If (childCount < K), then K is not present in Left 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.
While moving towards Right, we have to keep in mind that we already traversed
(childCount) lowest element in BST and now we need to find (K - childCount) node in
right sub tree
Repeat steps until node is not found.
Look at the below picture for better understanding of it.
Java Program to find Kth smallest element in BST using Second Approach.
package javabypatel.tree;
public class FindKSmallestElementInBinarySearchTree {
private Node rootNode;
public static void main(String[] args) {
new FindKSmallestElementInBinarySearchTree();
}
public FindKSmallestElementInBinarySearchTree() {
addNode(rootNode, 40);
addNode(rootNode, 20);
addNode(rootNode, 60);
addNode(rootNode, 10);
addNode(rootNode, 30);
addNode(rootNode, 50);
addNode(rootNode, 70);
printTreeInOrder(rootNode);
int kthSmallestElement = findKthSmallestItem(rootNode, 2);
if(kthSmallestElement!=-1){
System.out.println("Kth smallest node is :"+kthSmallestElement);
}else{
System.out.println("Kth smallest node is not found");
}
}
private int findKthSmallestItem(Node rootNode, int k) {
if(rootNode==null){
return -1; //Indication that kth smallest is not found.
}
int childCount = getNodeCount(rootNode.getLeft());
if(childCount+1==k){ // +1 for rootNode itself
return rootNode.getData();
}else if(childCount+1>=k){
return findKthSmallestItem(rootNode.getLeft(), k);
}else{
return findKthSmallestItem(rootNode.getRight(), 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 LARGEST 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