CareerCup

Solution does not exist. For a log(n) solution, you need to visit each level a constant number of times without traversing all the nodes, effectively eliminating as you go. Elimination is not possible in this case.

At the beginning, you are at the root and you can't have any idea where to go. You pick left or right. Without traversing all the nodes in that subtree, you can't even know if you are in the correct subtree. Getting the number of nodes there is already O(n). That's why Log(N) is impossible.

I think this question was meant to be asked for a complete BST.

so, for example BST has 8 nodes and it is unbalanced(node "1" in the root, root.right = 2, root.right.right=3, etc..).
the algorithm should find the kth smallest element(i.e. 6th smallest element which is 6) for logN steps(for 3 steps). Mission seems to be impossible..if the nodes are repeated then it become even more difficult..Does the solution even exist?

Viable solution , I gurantee, is augmenting the BST in such a way that each node stores the nodes in it's left subtree and right subtree. Then it is possilbe for lgn time for subsequent order statistics related query .

public void traverseToNThSmallest(Node root) {
			if (root.left != null) {
				traverseToNThSmallest(root.left);
			}
			counter++;
			if(counter ==nthElement)
			{
				System.out.println(nthElement+"th element: "+ root.val);
				return;
			}
			if (root.right != null) {
				traverseToNThSmallest(root.right);
			}
		}

public static int findKthElementinBSTInTimeOfLogN(treeNode root,int k){

int[] arr = BSTintoArray(root);

if(k>arr.length) return -1;

return arr[k-1];

}
public static int[] BSTintoArray(treeNode root){

if(root==null) return null;

int[] left = BSTintoArray(root.left);
int[] right = BSTintoArray(root.right);

int l_length = 0;
int r_length = 0;

if(left!=null) l_length = left.length;
if(right!=null)r_length = right.length;

int[] left_new = new int[l_length+1+r_length];
left_new[l_length]=root.data;
if(left!=null){
System.arraycopy(left, 0, left_new, 0, l_length);
}
if(right!=null){
System.arraycopy(right, 0, left_new, l_length+1, r_length);
}
return left_new;
}

number of nodes in the BST is known or unknown ?

find number of elements in left and right subtree. If n lies in left subtree then recursively search for (n - noOfElementsInRightSubtree). Same for right side if n lies in right subtree. The base case would be:

if(n == noOfElementsInLeftSubtree + 1)
    return root;

Isn't the Nth smallest mean the 1th highest ? :)

The approach that I'd use will be recusively go to the smallest node of BST (Left most node) and the recursively backtrack. While backtracking, keep the nodes in a stack. If the size of stack is n then the top element of stack is the result

Node temp;
public Node getNthMin(int target){
		if(target==1) return getMin();
		else{
			int counter=1;
			temp=getMin();
			while(true){			
			temp=temp.parent;
			counter++;
			if(counter==target) return temp;
			if(temp.right!=null) {counter++;}
			if(counter==target) return temp.right;
			}
		}
	}
	
	public Node getMin(){
		temp=root;
		while(true){
			if(temp.left==null) return temp;
			else temp=temp.left;
		}
		
	}

Node temp;
public Node getNthMin(int target){
		if(target==1) return getMin();
		else{
			int counter=1;
			temp=getMin();
			while(true){			
			temp=temp.parent;
			counter++;
			if(counter==target) return temp;
			if(temp.right!=null) {counter++;}
			if(counter==target) return temp.right;
			}
		}
	}
	
	public Node getMin(){
		temp=root;
		while(true){
			if(temp.left==null) return temp;
			else temp=temp.left;
		}
		
	}

nth smallest would be the nth InOrder successor ryt ?

node* nthsmallest(node * root, int n)
      {
            node* t = leftmost (root);    //Gives the leftmost node in bst

             for(int i=0;i<n-1;i++)
             {
                   node*p;
                   if(t->parent==0 || t->right!=0)
                                   p=leftmost(t->right)
                   else    //go up till we are on left side
                   {
                                         while((p=t->parent)!=0)
                                         {
                                                    if(t=p->left)
                                                           break;
                                                   t=p;
                                          }
                   }
                //Now p is the inorder successor
                t=p;
             }
      return t;
      }

In worst case you can't (say tree that looks like linked list) but on average you can probably do this.
start searching for the smallest with pointer1. After n steps start searching for the smallest in parallel with both pointer1 and new pointer 2. Once pointer1 reached the smallest pointer2 points to the nth smallest.

reach upto the leftmost node and the print tree in inorder upto count=6...
tell me if this will work or not???

Actually if traveling BST in-order, we will get the number by ascend, but most of us just do not realize this feature.
So this question will be changed into getting the kth element of BST in-order traverse.

void findK(Node* p, int& k) {
  if(!p || k < 0) return;
  findK(p->left, k);
  --k;
  if(k == 0) { 
    print p->data;
    return;  
  } 
  findK(p->right, k); 
}

Why don't we convert this BST into an AVL tree in O(logn) time and then search for the kth element in O(k) time? Is there a better solution?

int BinaryTree::nthSmallestItem(int nth){
	Stack<NodePtr> parent, rightChild;

	NodePtr ptr = root;
	int counter = nth;
	parent.push(ptr);
	while(!parent.empty() && counter > 0){
		while(ptr != 0){
			parent.push(ptr);
			if(ptr->right != 0)
				rightChild.push(ptr->right);
			ptr = ptr->left;
		}
		ptr = parent.topElement();
		parent.pop();
		counter--;
		if(counter == 0) break;
		if(ptr->right != 0){
			ptr  = rightChild.topElement();
			rightChild.pop();
		} else{
			// important to make ptr null else above while loop will probe same node and code goes into infinite loop
			ptr = 0;
		}
	}
	return ptr->data;
}

this would do the preorder of the tree which would give the nth smallest element in O(log n)complexity:
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
int data;
struct node *right;
struct node *left;
}*root=NULL;
struct node *bst_ins(struct node *root,int n)
{
struct node *temp=root,*temp1;
if(!root)
{
root=new node;
root->data=n;
root->right=NULL;
root->left=NULL;
}
else
{
temp=root;
while(temp)
{
temp1=temp;
if(n>temp->data)
temp=temp->right;
else
temp=temp->left;
}
temp=new node;
temp->data=n;
temp->right=NULL;
temp->left=NULL;
if(n>temp1->data)
temp1->right=temp;
else
temp1->left=temp;
}
return root;
}
int nth_smallest(struct node *root,int n,int count)
{
if(root->left)
count=nth_smallest(root->left,n,count);
count++;
if(count==n)printf("%d",root->data);
if(root->right)
count=nth_smallest(root->right,n,count);
return count;
}
int del_tree(struct node *root)
{
if(root)
{
del_tree(root->right);
del_tree(root->left);
}
delete root;
return 0;
}
int main()
{
int i,n,d;
printf("enter the number of elements to be inserted into the tree:\n");
scanf("%d",&n);
printf("enter the elements of the tree:\n");
for(i=0;i<n;i++)
{
scanf("%d",&d);
root=bst_ins(root,d);
}
printf("enter the nth smallest number to be searched:\n");
scanf("%d",&n);
nth_smallest(root,n,0);
del_tree(root);
return 0;
}

I also support that O(lgn) solution is not existing, but I try O(k) algorithm and I think I made it, here is my program in c, if there is anything wrong, please let me know about, thanks.

#include<iostream>
using namespace std;

typedef struct node_s {
	int value;
	struct node_s *left;
	struct node_s *right;
}BSTNode, *BSTree;

static int tree_size = 0;
int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
	if(!T) {
		*p = f;
		return 0;
	} else {
		if(T->value == value) {
			*p = T;
			return 1;
		} else if(value < T->value) {
			return tree_search(T->left, value, p, T);
		} else {
			return tree_search(T->right, value, p, T);
		}
	}
}

int tree_insert(BSTree *T, int value) {
	BSTNode *p = NULL;
	if(!tree_search(*T, value, &p, NULL)) {
		BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
		s->value = value;
		s->left = NULL;
		s->right = NULL;
		if(!(*T))
			*T = s;
		else if(value < p->value)
			p->left = s;
		else
			p->right = s;
		return 1;
	}
	return 0;
}

static int index = 0;
void find_k_th(BSTree T, int k, int *value) {
	if(T) {
		find_k_th(T->left, k, value);
		++index;
		if(index == k) {
			*value = T->value;
			return;
		}
		find_k_th(T->right, k, value);
	}
}

int get_value(BSTree T, int k) {
	int k_value = -1;
	if(k < 0 || k >= tree_size)
		return k_value;
	index = 0;
	find_k_th(T, k, &k_value);
	return k_value;
}

void in_traverse(BSTree T) {
	if(T) {
		in_traverse(T->left);
		cout << T->value << " ";
		in_traverse(T->right);
	}
}

int main(int argc, char *argv[]) {
	int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
	int len = sizeof(a) / sizeof(int);
	int i;
	BSTree T = NULL;
	for(i = 0; i < len; i++) {
		if(tree_insert(&T, a[i]))
			tree_size++;
	}
	in_traverse(T);
	cout << endl;
	int k = 4;
	cout << get_value(T, k) << endl;
	cin.get();
	return 0;
}

how about this?

Check for a balanced tree. if not balanced it?? or say cant do in log in

IF it is a balanced tree
Use log N steps to reach the minimum value where N is number of elements
and iteratively find successors till we get the nth smallest element.
This will take log N steps, n times
so O(logN) + O(nlogN) where n is a constant = O(logN)

first, start pre-order traversal of tree, when you visit node decrement count by 1,if count==0 return that element,,,,,initialize count by 'n'.

traverse the tree...
while traversing every node increment flag by 1..
for n th smallest element n==flag tht node is nth smallest element

Assumption: each node holds the number of nodes present within its subtree rooted at that node. If not for this assumption log N is not possible

Node * FindNSmallest(TNode *node, int N) {
        if(!node) return NULL;
	if(node->left->numNodes+1 == N) return node;
        if(node->left->numNodes>=N) return (FindNSmallest(node->left, N);
        else  return(FindNSmallest(node->right, N-node->left->numNodes-1);
}

it can be find in exact O(lon(n)+r) in worst case. and obviously it will be O(n) if bst is growing in only one way.
where n is total no of node in bst & r is the r'th element.

can't we solve it by run in order traversal and return on nth step, something like

var step = 0;
var value;
var prevvalue;
var n = 5;
tree.inOrderTraversal(function(node){
if(prevvalue != node.data)
  step++;
if(step==n)
    value = node.data;
prevvalue = node.data;  
  });
if(!value)
console.log('not enough nodes');
else
console.log(value);

?
it requires O(n)

maybe the solution only exist for balanced bst where number of nodes = 2^(h+1) - 1 where h is the tree height. the height can be found for log N time by traversing to the left until null node. then we found the subtree which has nth smallest elem( if n <= h+1 then it is in the left subtree we go in order to the left and stop on (h+1 - n) step.
the performance is O(lgN + (h + 1 - n)) = O (lg N * 2 - n) = O(lg N)

What if we do below:

1. Get the number of elements in left subtree in O(log n) time
2. if n < noOfElementInLeftSubtree then recurse in left sub tree
3. if n == noOfElementsInLeftSubtree + 1 then return root
4. else it has to be in right subtree so recurse in right subtree