CareerCup

Full java code

package org.sr;

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

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

public class NthLargestNodeInBST {

	/*
	 * static int curr; static int nThSmallest;
	 * 
	 * static int getNthSmallestNumber( Node root, int n) { curr = n; helper(root);
	 * return nThSmallest; }
	 * 
	 * static void helper(Node root) { if (root != null) { helper(root.left);
	 * curr--; if (curr == 0) { nThSmallest = root.data; return; }
	 * helper(root.right); }
	 * 
	 * }
	 */

	static int curr;
	static int nThLargest;

	static int getNthSmallestNumber(Node root, int n) {
		curr = n;
		helper(root);
		return nThLargest;
	}

	static void helper(Node root) {
		if (root != null) {
			helper(root.right);
			curr--;
			if (curr == 0) {
				nThLargest = root.data;
				return;
			}
			helper(root.left);
		}

	}

	public static void main(String args[]) {

		Node root = new Node(5);
		root.left = new Node(3);
		root.right = new Node(7);
		root.left.left = new Node(2);
		root.left.right = new Node(4);
		root.right.left = new Node(6);
		root.right.right = new Node(8);

		System.out.println(getNthSmallestNumber(root, 1));
		System.out.println(getNthSmallestNumber(root, 2));
		System.out.println(getNthSmallestNumber(root, 3));

	}
}

dat wud giv the Nth smallest node....do a reverse inorder to get the nth largest
inorder left node right
reverse norder right node left

Just do the inorder traversal of mirror image of BST.

Reverse of Inorder Traversal :
 
    Rev_Inorder( Tree* T ,int c ,int N )
     {
       if( T==Null )return;
       
          Rev_Inorder( T->right );
           Rev_Inorder( T->left );
             c++;
           if(c== N)
             print( T->data );

       }

Call : Rev_Inorder( T , 0 , N );

I think its not reverse inorder.
The line 'Rev_Inorder( T->left );' should be the last line in the function.

I think its not reverse inorder.
The line 'Rev_Inorder( T->left );' should be the last line in the function.

problems with recursive calls as well
nevertheless, not the correct solution..the counter c increases from top-down..i would guess it should happen bottom-up..for the largest element would be at the right most bottom

whereas in this case, the counter would invariably reach N at nth level from the root

I know that it's a stupid solution, but can we maintain a static variable in the function that is updated on each call and whenever the value becomes N we return the answer.

Rev_Inorder(Node* node, int& counter, int N)
{
if(node == null)return;


Rev_Inorder(node->right);

if(counter == N)
{

return;
}
count++;
print root->data;

Rev_Inorder(node->left);



}



Call: Rev_Inorder(root, 0, N)
The call will print the largest N number. Should be return after add the count, otherwise, the whole tree will be travasal

The N th largest node will also be (total nodes- N) smallest node. So we can do a simple in order traversal and stop when we reach the n nodes.
To know when we have reached the correct node we can keep a static variable

You can even go till the largest element and go through n-1 preceding elements to get to the answer

are you guys kidding me? inside the function Rev_Inorder, what else should be passed in other than node->right? how about the counter and N?

we have to play tricks on top N and counter!

Node* findNth(Node* tree, int& N)
{
if(n < 0 || tree == NULL) return NULL;
if(n == 0) return tree;

Node* rightRes = findNth(tree->right, n);

if(n <= 0) return rightRes;
if(n == 1) return tree;

return findNth(tree->left, n);
}

Each node has two counts: numLeft and numRight denoting number of nodes in its left and right subtrees respectively.

Node& getTheNode(const Node& curr, int N)
{
if(curr.numRight == N-1)
return curr;
else if(curr.numRight > N-1)
return getTheNode(curr.rightChild,N);
else // if(curr.numRight > N-1)
return getTheNode(curr.leftChild,N-1-curr.numRight);
}

O(log n) where n is the number of elements in the BST.

Each node has two counts: numLeft and numRight denoting number of nodes in its left and right subtrees respectively.

Node& getTheNode(const Node& curr, int N)
{
if(curr.numRight == N-1)
return curr;
else if(curr.numRight > N-1)
return getTheNode(curr.rightChild,N);
else // if(curr.numRight > N-1)
return getTheNode(curr.leftChild,N-1-curr.numRight);
}

O(log n) where n is the number of elements in the BST.

Not sure it's optimal:

1) get the smallest node in the tree (leftmost node)
2) call successor on the smallest node for n-1 times

Not sure about the time complexity, but might be better than 0(logn)

vector <int> vi;

void inOrder (NODE* root)
{
	if (root == NULL)
		return ;

	inOrder (root->left);

	vi.push_back(root->data);

	inOrder (root->right);

	return;
}

int sz = vi.size();
int target = vi [sz-N];

Keep a count variable while doing In Order Traversal of a BST. Return the element when the count = N