CareerCup

Traverse in reverse in-order (i.e. descending order).


Something like this (quick code without thinking, so bugs will be there).

Tree * Largest(Tree *root, const int k) {
    int count = 0;
    return LargestHelper(root, k, count);
}
// Return either NULL (not found), or returns the node.
Tree *LargestHelper(Tree *root, const int k, int &count) {
    if (root == NULL) {
        return NULL;
    }
    
    Tree *right = LargestHelper(root->right, k, count);
  
    if (right != NULL) return right;
   
    count++;
    if (count == k) {
        return root;
    }
       
    return LargestHelper(root->left, k, count);
}

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
} Node;

struct Node * kth_largest(struct Node *root, unsigned int k);
{
	if( ! root )
		return NULL;
	int pos = 0;
	return kth_largest_helper(root, k, &pos);
}

/* 
   Help find the kth_largest by comparing the rank of root from 
   the largest/rightmost node in the BST.
*/
struct Node *kth_largest_helper(struct Node *root, unsigned int k , int *rank)
{
	if( ! root )
		return root;

	struct Node *temp = NULL ;
	if( root-> right )
	{
		/* we have not seen the rightmost node yet => rank ordering has not started */
		temp = kth_largest_helper(root->right, k, rank);
	
		if ( temp )
			return temp;
	}
	(*rank)++; // increment position rank
	
	if( *rank == k )
		return root; // kth element

	return root->left ? kth_largest_helper(root->left, k, rank) : temp;
}

void kthlargest(struct Node *node,int k,int &index,int &res)
{
if(!node || index>k)
return;
kthlargest(node->right,k,index,res);
index++;
if(k==index)
{
res=node->data;
}
kthlargest(node->left,k,index,res);
}

My solution in Java. I created a class K to hold k since an int will not work with recursion.

Like the solutions above, it performs a reverse in-order traversal.

public class FindKthLargest {

	Node kthLargest(Node root, int ik) {
		// Create a new "K"
		K k = new K(ik);

		// Traverse the tree from largest to smallest
		return reverseIOT(root, k);
	}

	
	/**
	 * Traverse a subtree in reverse in-order (right,node,left)
	 * @param node	The subtree to traverse
	 * @param k		Exit with k.k == 0
	 * @return		The kth largest node
	 */
	private Node reverseIOT(Node node, K k) {
		if(node == null)
			return null;
	
		Node n = reverseIOT(node.right, k);
		if(n != null)
			return n;

		if(--k.k == 0)
			return node;
			
		return reverseIOT(node.left, k);
	}


	/**
	 * Node class as defined by problem
	 */
	private static class Node {
		private Node(int value) {
			this.value = value;
		}
		private final int value;
		private Node left;
		private Node right;
		
		public String toString() {
			return String.valueOf(value);
		}
	}


	/**
	 * This class holds a mutable integer
	 */
	private class K {
		private int k;
		
		private K(int k) {
			this.k = k;
		}
	}
	
	
	
	/**
	 * Test harness
	 * @param args	Ignored
	 */
	public static void main(String args[]) {
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		
		node4.left  = node2;
		node4.right = node6;
		node2.left  = node1;
		node2.right = node3;
		node6.left  = node5;
		node6.right = node7;
	
		FindKthLargest app = new FindKthLargest();

		System.out.println(app.kthLargest(node4, 5));
	}

}

traverse inorder, return the kth node traversed

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

typedef struct tree
{
int data;
struct tree* left;
struct tree* right;
}TREE;


TREE* createNode(int x)
{
TREE *ptr;
ptr=(TREE*)malloc(sizeof(TREE));
ptr->data=x;
ptr->left=NULL;
ptr->right=NULL;
return ptr;
}






void kthLargest(TREE *root,int *kth,int k)
{
static int counter=0;
if(root==NULL)
return;
else
{



kthLargest(root->left,kth,k);
counter=counter+1;
if(k==counter)
{
*kth=root->data;
return;

}

printf("%d",counter);
kthLargest(root->right,kth,k);


}


}
int getCount(TREE *ptr)
{
if(ptr==NULL)
return 0;
else
return 1+getCount(ptr->left)+getCount(ptr->right);

}

TREE *root;
void initialize()
{
root=NULL;
}

int main()
{

initialize();
root=createNode(8);
root->left=createNode(6);
root->right=createNode(11);
root->left->left=createNode(5);
root->left->right=createNode(7);
root->left->left->left=createNode(4);
root->right->left=createNode(10);
root->right->right=createNode(13);
int kth,k;
k=5;
kth=0;
kthLargest(root,&kth,getCount(root)-k+1);
printf("\n the kth largest number =%d",kth);
return 0;

}

traverse the tree in inorder try to find kth_temp element which is equal to kth_temp=number of nodes - (k-1).
Suppose taking above comment example kth_temp = 8(num of nodes)-(2(k)-1)=7th.
and 7th element is 99 that is the answer.

1) count the total number of nodes in the BST,one pass traversal,time cost:O(n)
2) traverse inorder, the (n-k+1)-th smallest node is the answer,time cost:O(n)
below are the C++ code

int CountNode(Node* root)
{
	if(root==NULL)return 0;
	return 1+ CountNode(root->left) + CountNode(root->right);
}
Node * kth_smallest(Node *root, unsigned int k)
{
	if(root == NULL)return NULL;
	Node* ans = kth_smallest(root->left,k);
	if(ans != NULL)return ans;
	if(k==1)return root;
	k--;
	return kth_smallest(root->right,k):
}
Node * kth_largest(Node *root, unsigned int k)
{
	int n = CountNode(root);
	return kth_smallest(root,n-k+1);
}

Node iterativeInorderForKthLargest(Node root, int k) {
	Stack s = new Stack();
	s.push(new NodeWatchedCount(root, 1));
	int currentLargest = 0;
	while(!s.isEmpty()) {
		NodeWatchedCount n = s.pop();
		if(n.count == 2) {
			currentLargest++;
			if(currentLargest == k) {
				return n.node;
			}
			s.push(new NodeWatchedCount(n.node.right, 1));
		} else {
			n.count = 2;
			s.push(n);
			s.push(n.left);
		}
	}
}

NodeWatchedCount {
	int count;
	Node node;
}

if k < n/2 then it will be in right subtree
else it'll be in right subtree
halve the limit and repeat until there is only 1 element between previous iteration and current iteration which will be the kth largest number

O(log(n))

right, root, left traversal

Hello,
I have a inorder method to solve this problem.
I used showell30@yahoo.com's code to create the BST, thanks.

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

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
};
typedef struct Node node_t;

void find_by_inorder(node_t *root, int *count, node_t **result, int k)
{
    if (root != NULL) {
        find_by_inorder(root->right, count, result, k);
        (*count)++;
        if (*count == k) {
            *result = root;
            return;
        }
        find_by_inorder(root->left, count, result, k);
    }
}

node_t *make_node(int n) {
    node_t *node = malloc(sizeof(node_t));
    node->left = NULL;
    node->right = NULL;
    node->val = n;
    return node;
}

int main(int argc, char **argv) {
    node_t *node;
    node_t *t1 = make_node(1);
    node_t *t2 = make_node(2);
    node_t *t3 = make_node(3);
    node_t *t4 = make_node(4);
    node_t *t5 = make_node(5);
    node_t *t6 = make_node(6);
    t2->left = t1;
    t2->right = t3;
    t4->left = t2;
    t4->right = t5;
    t5->right = t6;
    node_t *result = NULL;
    int count = 0;
    int i;
    for (i = 0; i < 10; i++) {
        find_by_inorder(t4, &count, &result, i);
        if (result != NULL)
            printf("%dth: %d\n", i, result->val);
        result = NULL;
        count = 0;
    }
    return 0;
}

As everybody has figured out we can solve it in O(n) using inorder:

node *kthLargest(node *root, int &k){
    if(root == NULL)
        return NULL;
        
    node *n = kthLargest(root->left, k);
    if(n != NULL) return n;
    k -=1;
    if(k == 0) return root;
    
    n = kthLargest(root->right, k);
    return n;
}

But, if we are allowed to modify the tree node, we can add "size" integer member in it and then sizeify the tree. root->size = size of the subtree rooted at root.
Here is a code snippet to calculate the size of all the possible subtrees:

int sizeifyBST(node *&root){
    if(root == NULL){
        return 0;
    }
    
    int leftsize = sizeifyBST(root->left);
    int rightsize = sizeifyBST(root->right);
    return root->size = leftsize + rightsize + 1;
}

Now, we can easily find kth largest in O(logn):
suppose we are at node T:
1. k == size of the left subtree + 1, then return T
2. if k > size of the left subtree + 1, then recursively call the same method with k = k - size of the left subtree
3. if k < size of the left subtree, then go left with same k

node *findKthLargestFaster(node *root, int k){
    if(root == NULL) return NULL;
    
    int leftsubtreesize = root->size
                            - (root->right?root->right->size:0)
                            - 1;
    
    if(k == leftsubtreesize + 1)
        return root;
    else if(k < leftsubtreesize + 1)
        return findKthLargestFaster(root->left, k);
    else
        return findKthLargestFaster(root->right, k - leftsubtreesize-1);
}

Here is the link to the working code, if you guys are interested:
ideone.com/Qkkkl6

Solution in C:

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

typedef struct Node {
  int val;
  struct Node *left;
  struct Node *right;
} Node;

static Node* dokth_largest(Node* n, unsigned int* k)
{
  if ( ! k )
    return NULL;
  Node* tmp = NULL;
  if ( n->left )
    tmp = dokth_largest(n->left, k);
  if ( tmp )
    return tmp;
  if ( *k == 0 )
    return n;
  --(*k);
  if ( n->right )
    tmp = dokth_largest(n->right, k);
  return tmp;
}

Node* kth_largest(Node *root, unsigned int k)
{
  return dokth_largest(root, &k);
}

int main()
{
  Node n1 = { 1, NULL, NULL };
  Node n3 = { 3, NULL, NULL };
  Node n2 = { 2, &n1, &n3 };
  Node n5 = { 5, NULL, NULL };
  Node n6 = { 6, &n5, NULL };
  Node n4 = { 4, &n2, &n6 };
  Node* n = kth_largest(&n4, 4);
  if ( n )
    printf("%d\n", n->val);
  else
    printf("not found\n");
}

Java version:

static class Node {
		int val;
		Node right = null;
		Node left = null;
	}

	static int countNodes(Node root) {
		if (root == null)
			return 0;
		else
			return countNodes(root.left) + 1 + countNodes(root.right);
	}

	private static Node kthLargest(Node root, int k) {
		if (k == 0 || root == null)
			return null;
		int r = countNodes(root.right);
		if (r == k-1) return root;
		else if (r>=k) return kthLargest(root.right, k);
		else return kthLargest(root.left, k-r-1);
	}

/// Using Some Method Like mid-order Trans

TNode * kth_largest(TNode * root, int k, int & count)
{
    if(NULL == root) return NULL;
    TNode * r1 = kth_largest(root->right, k, count);
    if(NULL != r1) return r1; 
    count ++; 
    if(k == count) return root;
    TNode * r2 = kth_largest(root->left, k, count);
    if(NULL != r2) return r2; 
    return NULL;
}

A solution using Inorder iterator, and call Next() k times.

class InOrderIterator
{
public:
    InOrderIterator(const Node* const root)
    {
        TraverseLeftMostPath(root);       
    }

    const Node* Next()
    {
        if (m_stack.size() == 0) return NULL;

        const Node* curNode = m_stack.Pop();
        if (curNode->Right)
        {
            TraverseLeftMostPath(curNode->Right);
        }
        return curNode;
    }
private:
    void TraverseLeftMostPath(const Node* const node)
    {
        while (node && node->Left)
        {
            m_stack.Push(node);
            node = node->Left;
        }
    }
    Stack<shared_ptr<Node>> m_stack;
}

const Node* root = CreateTree(1000);
InOrderInterator iterator(root);
for (size_t i = 0; i < k; ++i)
{
    printf_s("%s\n", iterator.Next()->ToString());
}

The famous algorithms book -- "Introduction to Algorithms" actually contains a solution
to the problem. It's idea is to first find the minimum node of the tree, and then traverse from it and find its kth SUCCESSOR.

Please check out the detials from 12.2-7, Chapter 12 of CLRS, Second edition.

FIND-KTH-LARGEST(x, k)
    x = TREE-MINIMUN(x)
    while k > 0
        x = TREE-SUCCESSOR(x)
        k = k - 1
    return x

where procedures TREE-MINIMUN and TREE-SUCCESSOR have been given in previous pages.

Node *find_k_largest_node(Node *n, int k) {
stack<Node*> s;
bool done = false;

while (!done) {
if (n) {
s.push(n);
n = n->left;
}
else {
if (s.empty()) {
done = true;
}
else {
n = s.top();
s.pop();

k--;

if (k == 0) {
return n;
}

n = n->right;
}
}
}

return NULL;
}

public class SelectionOnBST {
	
	class Node {
		int v;
		Node left, right;
		
		public Node(int v){
			this.v = v;
			left = right = null;
		}
	}
	
	static class Pair {
		Node n;
		int x;
		
		public Pair(Node n, int x){
			this.n = n;
			this.x = x;
		}
	}
	
	public SelectionOnBST() {
	}

	/**
	 * Assume read only nodes, cannot store heights
	 */
	static Node findKthLargestElement(Node root, int k){
		Pair p = helper(root, k);
		if( p == null){
			return null;
		} else {
			return p.n;
		}
	}
	
	static Pair helper(Node root, int k){
		int numExamined = 0;
		if(root == null || k <=0){
			return new Pair(null,0);
		} else if(root.right == null && root.left == null){
			numExamined = 1;
			if(k == 1){
				// found
				return new Pair(root, k);
			} else {
				return new Pair(null, 1);
			}
		} else if(root.right != null){
			Pair p = helper(root.right,k);
			numExamined = p.x;
			if(numExamined == k){
				// found
				return p;
			}
		}
		
		if(numExamined == (k-1)){
			// found
			return new Pair(root,k);
		} else {
			numExamined++;
		}
		
		if(root.left != null){
			Pair p = helper(root.left, k-numExamined);
			// found
			if(p.n != null){
				p.x = k;
				return p;
			} else {
				numExamined += p.x; 
			}
		}
		
		return new Pair(null,numExamined);
	}
}