CareerCup

do the inorder traversal and return the k th element......

Node* kSmallest(Node* curr, int* k){
	Node* result = NULL;
	
	if (NULL != curr) {
		result = kSmallest(curr->left, k);
		
		if (NULL == result ) {
			(*k)--;

			if (k == 0) {
				result = curr;
			}
			else {
				result = kSmallest(curr->right, k);
			}
		}
	}
	return result;
}

Node* findSmallest(Node* curr, int k) {
	int smallest = k;
	return kSmallest(curr, &smallest);
}

How do you even know this is bar raiser round?

Node* kSmallest(Node* curr, int k, int *count){
	if(!curr) return NULL;

	else{
		Node* left, right;
		left = kSmallest(curr->left, k, count);

		if(left) return left;
		
		*count++;
		if(*count==k) return curr;

		right = kSmallest(curr->right, k, count);

		if(right) return right;

		return NULL;
	}

}

Node* printKth(struct node * root, int k)
{
 static int count = 1;
 if(root != NULL)
 {
   Node * res;

   res =  printKth(root->left, k);
   if(res) return res;
   
   
   if(k == count)
	return root;

   count++;

   res = printKth(root->right, k);
   if(res) return res;
 }
  return NULL;

}

This can be done by a recursive inorder traversal of the BST and keeping global value to know when you reach the kth smallest number. Assume k is 4, the following code will assign and return the target node if found.

static int k =4;

	public static Node inOrderTraversal( Node node, Node target ){
		if(node == null)return null;
		inOrderTraversal(node.leftNode, target );
		if(--k==0) target= node;
		inOrderTraversal(node.rightNode, target);
		return target;
	}

Below is the complete code and the driver program to return the k-th minimum node in the BST, with all the corner case tests implemented. Just do an in-order traversal of the BST nad count the number of the nodes processed up to the current point. As soon as the counter (initially set to "k") turns 0, we know that we have reached the k-th minimum node, so return it.

#include <stdio.h>
#include <stdlib.h>

////////////////////////////////////////////////////////////////////////////////
struct Node {
    int data;
    Node* left;
    Node* right;    
    Node() : data(-1), left(NULL), right(NULL) {};
};

bool bst_add_node(Node* root, Node* newnode)
{
    if (NULL == root || NULL == newnode)
        return false;
    
    if (newnode->data <= root->data) {
        if (NULL == root->left){
            root->left = newnode;
            return true;
        }
        else { // the left node exists
            return bst_add_node(root->left, newnode);
        }
    }
    else { // the new node's value is GT the root's value
        if (NULL == root->right){
            root->right = newnode;
            return true;        
        }
        else {
            return bst_add_node(root->right, newnode);
        }
    }
    return true;
}

bool bst_add_value(Node* root, const int& val)
{
    Node* newnode = new Node;
    newnode->data = val;
    return bst_add_node(root, newnode);
}

void print_bst(Node* root)
{
    if (root->left)
        print_bst(root->left);
    
    printf("%d\n", root->data);
    
    if (root->right)
        print_bst(root->right);    
}

////////////////////////////////////////////////////////////////////////////////

/** Do an in-order of the BST here */
void kthmin(Node* node, Node*& retnode, int& k)
{
    if (node->left)
        kthmin(node->left, retnode, k);
    
    // Process the node itself    
    --k;
    if (0 == k) {
        //print_node(node);
        retnode = node;
        return;
    }
    
    if (node->right)
        kthmin(node->right, retnode, k);
}

int main(int argc, char* argv[])
{
    Node root;
    Node* kthnode = NULL;
    int kth = 1;
    int kthstore = kth;
       
    int arr[] = { 5, 1, 12, 24, 38, 20, 15, 6, 83, 33 };
    int cnt = sizeof(arr) / sizeof(arr[0]);
    
    if (argc > 1) {
        kth = atoi(argv[1]);
        kthstore = kth;
    }
        
    root.data = 18;
    
    // Add some values to the BST
    for (int i = 0; i < cnt; ++i){
        bst_add_value(&root, arr[i]);    
    }
    
    kthmin(&root, kthnode, kth);
    
    print_bst(&root);
    
    if (kthnode)
        printf("%d-th minimum node value: %d\n", kthstore, kthnode->data);
    else
        printf("%d-th minimum node not found\n", kthstore);

    return 0;

}

1. If it's a perfect binary tree and total number of nodes in the tree are known, then we can find the Kth largest or smallest element in log(n) time, because at each step we can reject one subtree. In fact we can predict the path just by using simple maths.
2. If it's just any binary search tree then doing the inorder traversal is the most optimum solution and will take O(n) time (obviously).

public Node GetKthSmallest(Node node, int k out)
{
	if (node == null || k <= 0)
		return null;

	Node node = GetKthSmallest(node.Left, k out);
	if (node != null)
		return node;
	

	k--;
	if (k == 0) return node;

	Node node = GetKthSmallest(node.Right, k out);
	if (node != null)
		return node;
	
	return null;
}

public Node GetKthSmallest(Node node, int k out)
{
	if (node == null || k <= 0)
		return null;

	Node node = GetKthSmallest(node.Left, k out);
	if (node != null)
		return node;
	

	k--;
	if (k == 0) return node;

	Node node = GetKthSmallest(node.Right, k out);
	if (node != null)
		return node;
	
	return null;
}

more like the bar lowering round

you need to store the size of left and right subtrees at every node

Seems too easy to be a bar raiser.

Input: BST (root node), and int k
Output: kth smallest node from the BST

Brainstorm:
- In order traversal to array n
- Return node where (k - 1)th element of array n

Complexity:
- O(log n) time
- O(n) space

*** However, I'm assuming this could be done in O(1) and O(logn) WC by short circuiting the recursion when kth element is traversed.

private ArrayList<Node> kthElementBST(Node root, ArrayList<Node> elements) {
    if(root.next == null && root.right == null) {
        elements.add(root);
        return elements;
    }
    
    elements.add(kthElementBST(root.left, elements));
    elements.add(root);
    elements.add(kthElementBST(root.right, elements));
    
    return elements;

}