WAP to Find kth Maximum & Minimum in BST

#include
#include
#include


/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}


int kthMax(struct node* t, int *k) {

if(t == NULL)
return INT_MIN;

int x = kthMax(t->right, k);

if(x != INT_MIN) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMax(t->left, k);
}


int kthMin(struct node* t, int *k) {

if(t == NULL)
return INT_MAX;

int x = kthMin(t->left, k);

if(x != INT_MAX) return x;

(*k)--;
if(*k == 0) return t->data;

return kthMin(t->right, k);
}


/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

int n=5,m=5;
printf("Given Min in BST is %d \t Max is=%d", kthMin(root,&n),kthMax(root,&m));
getchar();
return 0;
}

Java program to doing the Same

import java.util.Random;
import java.util.Stack;


public class BinaryTree {

private static int N = 7;
private static Node root = null;
public static int K = 3;
private static int INDEX = 0;
public static void main(String [] args) {
root = buildBST(root);
System.out.println("Printing inorder: ");
inorder(root);
System.out.println();
System.out.println("K value: " + K);
findKthSmallestIterative(root);
findKthSmallesRecursive(root);
}

public static void findKthSmallesRecursive(Node node) {
Stack stack = new Stack();
int i=1;
while (!stack.isEmpty() || node != null) {

if (node == null) {
node = stack.pop();
if (i == K) {
System.out.println("Kth Node :" + node.data);
}
++i;
node = node.right;
}
if (node != null) {
stack.push(node);
node = node.left;
}
}
}

public static void findKthSmallestIterative(Node node) {
if (node == null) {
System.out.println("Tree is empty!!");
return;
}
if (node.left != null) {
findKthSmallestIterative(node.left);
}

++INDEX;
if (K == INDEX) {
System.out.println("Kth Smallest Node Value: " + node.data);
return;
}

if (node.right != null) {
findKthSmallestIterative(node.right);
}
}

public static void inorder(Node node) {
if (node == null) { return ; }

if (node.left != null) {
inorder(node.left);
}
System.out.print(node.data + " ");
if (node.right != null) {
inorder(node.right);
}
}

public static Node buildBST(Node node) {
Random rand = new Random();

for (int i=0; i int value = rand.nextInt(99) + 1;
node = buildBST(node, value);
System.out.print(value + " ");
}
System.out.println();

return node;
}

private static Node buildBST(Node node, int data) {
if (node == null) { return new Node(data); }

if (data <= node.data) {
node.left = buildBST(node.left, data);
} else {
node.right = buildBST(node.right, data);
}
return node;
}
}

class Node {
Node left;
Node right;
int data;

Node(int data) {
this.data = data;
left = null;
right = null;
}
}


TC O(n)
SC O(1)
Run Here https://ideone.com/TeT4E