CareerCup

Traverse right,center and left. Inorder in opposite direction.

Code:

int count=0;
public void findKthLargest(BinarySearchTree root, int K) {
		if (root != null) {
			findKthLargest(root.getRight(), K);
			count++;
			if (count == K)
				System.out.println(root.getData());
			findKthLargest(root.getLeft(), K);
		}
	}

Logic will be traversing tree (right root left) and one counter to keep track of no of nodes being traversed.If counter equals k print the node.

int counter=0;
Public Node order(Node root, int k)
{
If(root!=null)
{
Node temp=order(root.right);
If(temp!=null)
return temp;
counter++
if(counter==k)
return root;
return order(root.left);
}
return null;
}

The above algorithm takes O(n) time to find the kth largest element in BST. Please someone suggest any other approach which takes <O(n) if there is any.

Recursive code:

public static Node ReturnKthItem(Node root, int k){ 
            int currPosition = 0;
            Node kthNode = null;
            ReturnKthItem(root, k, ref currPosition, ref kthNode);
            return kthNode;
        }

        private static bool ReturnKthItem(Node root, int k, ref int currPosition, ref Node kthNode){
            if (root == null)
                return false;
            if (!ReturnKthItem(root.Right, k, ref currPosition, ref kthNode)){
                currPosition = currPosition + 1;
                if (k == currPosition){
                    kthNode = root;
                    return true;
                }
                else if (ReturnKthItem(root.Left, k, ref currPosition, ref kthNode)){
                    return true;
                }
                else{
                    return false;
                }
            }
            else{
                return true;
            }
        }

Node findkthElement(TreeNode root , int k ) {
  if (root == null) return root ; 

  int countLeft = coundNodes(root.left) [ 
  
  if(k == countLeft + 1)  return root ; 
  if(k <= countLeft) {
   findkthElement(root.left, k-1);
  } 
 else {
  findkthElement(root.right, k-(countLeft+1));
 }
}

Algo
1> Create a stack to hold the references of the BST nodes. Set the counter variable to 0. Start from root. Make it the "current node".
2> Start from the "current node". Go on traversing the right child until the node which does not have a right child. en-stack it. Increase the counter variable by 1.
2a> If the value of counter is k, return the value of the node at the top of the stack.
2b> Else check whether the top node has left child. if yes make the left child the
current node. Again execute step 2.
2c> Else if the top node does not have a left child, destack the stack node by node till
it is empty. With every de-stack operation hold the reference of the node in a single
variable. So when the stack is empty the variable holds the lowest reference of the stck.
If this is the root node throw error. Because k>n. Else make the parent of this node
the "current node" and execute step 2.

Non Recursive:

public static Node ReturnKthItemNonRecursive(Node root, int k){
            if (k <= 0 || root == null)
                return null;
            int i = 0;
            Node node = root;
            Stack<Node> stk = new Stack<Node>();
            while (node != null){
                do{
                    stk.Push(node);
                    node = node.Right;
                } while (node != null);
                node = stk.Pop();i++;
                do{
                    if (i == k)
                        return node;
                    if (node.Left == null){
                        if (stk.Count == 0)
                            return null;
                        node = stk.Pop();i++;
                    }
                } while (node.Left != null);
                node = node.Left;
            }
            return null;
        }

public Node kthLargest(Node node, int k) {
		if (node != null) {
			kthLargest(node.rightChild, k);
			k--;
			if (k == 0) {
				return root;
			}
			kthLargest(node.leftChild, k);
		}
		return null;
	}

The basic premise is the same: Recursively traverse to the right, then start counting down until you have the desired node. Here is a c++ version:

Node *getK(Node* r, int &k) {
	if (!r) return NULL;
	Node* ret = getK(r->right, k);
	if (ret) return ret;
	if (!k) return r;
	k--; //remember, k is a reference, so this value will propogate to other calls
	return getK(r->left, k);
}

For this, each node must contain a field with number of nodes in its left subtree. Suppose that root has m nodes in left sub tree. if k<= m we recursively search for kth smallest element in its left sub tree. If k = m+1 then the current node is kth smallest element. If k >m+1 then we recursively search for k-m-1 smallest element in its right sub tree.

int count = 0;
function findKthElement(Node * root) {
if(root == null) return;
if(count == k) return root->data;
findKthElement(root->right);
findKthElement(root->left);
count ++;
}

Go for right, root , left order recursively.

C++ version. Avoid unnecessary recursion to the left subtree after the element has already been found.

#include <iostream>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <vector>

template <typename T>
struct bst_node {
	bst_node(T data) : left_(nullptr), right_(nullptr), data_(data) { }
	~bst_node() { delete left_; delete right_; }
	
	bst_node<T>* left_;
	bst_node<T>* right_;
	T data_;
};

template <typename T, typename RandIt>
bst_node<T>* create_bst_r(RandIt beg, RandIt end) {
	if (beg > end)
		return nullptr;

	RandIt mid = beg + (end - beg) / 2;
	bst_node<T>* node = new bst_node<T>(*mid);
	node->left_ = create_bst_r<T>(beg, mid - 1);
	node->right_ = create_bst_r<T>(mid + 1, end);
	return node;
}

template <typename T, typename RandIt>
bst_node<T>* create_bst(RandIt beg, RandIt end) {
	return create_bst_r<T>(beg, end - 1);
}

template <typename T>
void find_kth_largest_r(bst_node<T>* node, size_t kth, size_t& pos, T& largest) {
	if (!node || pos == kth)
		return;

	// Find the largest node by traversing right
	find_kth_largest_r(node->right_, kth, pos, largest);

	// Increment counter and check if it's kth
	if (++pos == kth) {
		largest = node->data_;
		return;
	} else if (pos > kth) {
		// No need to recurse again. We already found our element.
		return;
	}

	// Also traverse left
	find_kth_largest_r(node->left_, kth, pos, largest);
}

template <typename T>
T find_kth_largest(bst_node<T>* root, size_t kth) {
	T largest = T();
	size_t zero = 0;
	find_kth_largest_r(root, kth, zero, largest);
	return largest;
}

int main() {
	std::vector<int> arr{1, 2, 3, 4, 5, 6, 7, 8, 9};
	std::unique_ptr<bst_node<int>> root(create_bst<int>(std::begin(arr), std::end(arr)));
	std::cout << "4th largest: " << find_kth_largest(root.get(), 4) << std::endl;
}