Given root of binary search tree and K as input, find K-th smallest element in BST.
https://gyaneshwarpardhi.wordpress.com/2014/06/14/find-kth-smallest-element-in-binary-search-tree/
http://karmaandcoding.blogspot.com/2011/04/kth-smallest-element-in-binary-search.html
Method 2: Augmented Tree Data Structure.
The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.
Order statistic tree(顺序统计树)是一种BST的变种，往每个node里面加上一个field来存左子树的节点数，在树平衡时可以达到O(logN)复杂度。
这种树在很多题目中都可以用到。
http://www.dsalgo.com/2013/03/find-kth-smallest-element-in-binary.html
The idea is to keep track of popped elements which participate in the order statics.
http://karmaandcoding.blogspot.com/2011/04/kth-smallest-element-in-binary-search.html
Not efficient solution
http://algorithmsandme.com/2013/08/find-kth-smallest-element-in-binary-search-tree/
Find the kth largest element in a Binary Search Tree
public static void getElement(Tree root, int k){
//Base condition
if(root == null)
return;
getElement(root.right, k); //first traverse the right sub tree
if(++index == k){
System.out.println(root.data);
return;
}
getElement(root.left, k); //then traverse the left sub tree
}
http://www.zrzahid.com/kth-smallestminimum-element-in-a-bst-rank-of-a-bst-node/
http://www.geeksforgeeks.org/kth-smallest-element-in-bst-using-o1-extra-space/
Read full article from Find k-th smallest element in BST (Order Statistics in BST) | GeeksforGeeks
https://gyaneshwarpardhi.wordpress.com/2014/06/14/find-kth-smallest-element-in-binary-search-tree/
static int kthSmallestElementInTheTree(treeNode* rootNode,int k, int *count){ if(rootNode==NULL) return 0; //check if kth element in left subtree of rootNode int kthEle = tree::kthSmallestElementInTheTree(rootNode->leftChild,k,count); //yes we found and return if(kthEle) return kthEle; //when count is equal to k then return current node value if(++*count==k) return rootNode->val; //check in right subtree of rootNode return tree::kthSmallestElementInTheTree(rootNode->rightChild,k,count);}Method 2: Augmented Tree Data Structure.
The idea is to maintain rank of each node. We can keep track of elements in a subtree of any node while building the tree. Since we need K-th smallest element, we can maintain number of elements of left subtree in every node.
Assume that the root is having N nodes in its left subtree. If K = N + 1, root is K-th node. If K < N, we will continue our search (recursion) for the Kth smallest element in the left subtree of root. If K > N + 1, we continue our search in the right subtree for the (K – N – 1)-th smallest element. Note that we need the count of elements in left subtree only.
Order statistic tree(顺序统计树)是一种BST的变种，往每个node里面加上一个field来存左子树的节点数，在树平衡时可以达到O(logN)复杂度。
这种树在很多题目中都可以用到。
http://www.dsalgo.com/2013/03/find-kth-smallest-element-in-binary.html
if K = root.leftElement + 1 root node is the K th node. goto stop else if K > root.leftElements K = K - (root.leftElements + 1) root = root.right goto start else root = root.left goto srart
int k_smallest_element(node_t *root, int k){ int ret = -1; if( root ) { /* A crawling pointer */ node_t *pTraverse = root; /* Go to k-th smallest */ while(pTraverse) { if( (pTraverse->lCount + 1) == k ) { ret = pTraverse->data; break; } else if( k > pTraverse->lCount ) { /* There are less nodes on left subtree Go to right subtree */ k = k - (pTraverse->lCount + 1); pTraverse = pTraverse->right; } else { /* The node is on left subtree */ pTraverse = pTraverse->left; } } } return ret;}struct node_t{ int data; int lCount; node_t* left; node_t* right;};/* Iterative insertion Recursion is least preferred unless we gain something*/node_t *insert_node(node_t *root, node_t* node){ /* A crawling pointer */ node_t *pTraverse = root; node_t *currentParent = root; // Traverse till appropriate node while(pTraverse) { currentParent = pTraverse; if( node->data < pTraverse->data ) { /* We are branching to left subtree increment node count */ pTraverse->lCount++; /* left subtree */ pTraverse = pTraverse->left; } else { /* right subtree */ pTraverse = pTraverse->right; } } /* If the tree is empty, make it as root node */ if( !root ) { root = node; } else if( node->data < currentParent->data ) { /* Insert on left side */ currentParent->left = node; } else { /* Insert on right side */ currentParent->right = node; } return root;}
http://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/
http://www.geeksforgeeks.org/kth-largest-element-in-bst-when-modification-to-bst-is-not-allowed/
node_t *k_smallest_element_inorder(stack_t *stack, node_t *root, int k){ stack_t *st = stack; node_t *pCrawl = root; /* move to left extremen (minimum) */ while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and process each node */ while( pCrawl = pop(st) ) { /* each pop operation emits one element in the order */ if( !--k ) { /* loop testing */ st->stackIndex = 0; break; } /* there is right subtree */ if( pCrawl->right ) { /* push the left subtree of right subtree */ pCrawl = pCrawl->right; while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and repeat */ } } /* node having k-th element or NULL node */ return pCrawl;}void kthLargestUtil(Node *root, int k, int &c){ // Base cases, the second condition is important to // avoid unnecessary recursive calls if (root == NULL || c >= k) return; // Follow reverse inorder traversal so that the // largest element is visited first kthLargestUtil(root->right, k, c); // Increment count of visited nodes c++; // If c becomes k now, then this is the k'th largest if (c == k) { cout << "K'th largest element is " << root->key << endl; return; } // Recur for left subtree kthLargestUtil(root->left, k, c);}// Function to find k'th largest elementvoid kthLargest(Node *root, int k){ // Initialize count of nodes visited as 0 int c = 0; // Note that c is passed by reference kthLargestUtil(root, k, c);} private void add(Node root, int num)
{
Node node = new Node(num);
if (node.value < root.value)
{
root.leftWeight++;
if (root.left == null)
root.left = node;
else
add(root.left, num);
} else
{
if (root.right == null)
root.right = node;
else
add(root.right, num);
}
}
public int getOrdered(int k)
{
return getOrdered(root, k);
}
private Integer getOrdered(Node root, int k)
{
if (root == null)
return null;
if (root.leftWeight > k)
{
return getOrdered(root.left, k);
} else if (root.leftWeight < k)
{
return getOrdered(root.right, k - root.leftWeight);
} else
{
return root.value;
}
}
Method 1: Using Inorder Traversal.node_t *k_smallest_element_inorder(stack_t *stack, node_t *root, int k){ stack_t *st = stack; node_t *pCrawl = root; /* move to left extremen (minimum) */ while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and process each node */ while( pCrawl = pop(st) ) { /* each pop operation emits one element in the order */ if( !--k ) { /* loop testing */ st->stackIndex = 0; break; } /* there is right subtree */ if( pCrawl->right ) { /* push the left subtree of right subtree */ pCrawl = pCrawl->right; while( pCrawl ) { push(st, pCrawl); pCrawl = pCrawl->left; } /* pop off stack and repeat */ } } /* node having k-th element or NULL node */ return pCrawl;}
public static void findKthSmallesRecursive(Node node) { Stack<node> stack = new Stack<node>(); int i=1; while (!stack.isEmpty() || node != null) { if (node == null) { node = stack.pop(); if (i == K) { System.out.println("Kth Node :" + node.data); } ++i; node = node.right; } if (node != null) { stack.push(node); node = node.left; } } }http://algorithmsandme.com/2013/08/find-kth-smallest-element-in-binary-search-tree/
Tech Savvy: Find the kth largest element in a Binary Search Treeint find_kth_node(Node *root, int K){if(!root)return 0;int no_left = find_size_of_left_tree(root->left);/* If there are K-1 nodes in left sub tree */if(no_left == K-1){return root->value;}/* If there are more than K-1 nodes in left sub tree */else if(no_left > K-1){return find_kth_node(root->left, K);}/* If there are less than K nodes in left sub tree */else{return find_kth_node(root->right, K-no_left-1);}}
Find the kth largest element in a Binary Search Tree
public static void getElement(Tree root, int k){
//Base condition
if(root == null)
return;
getElement(root.right, k); //first traverse the right sub tree
if(++index == k){
System.out.println(root.data);
return;
}
getElement(root.left, k); //then traverse the left sub tree
}
http://www.zrzahid.com/kth-smallestminimum-element-in-a-bst-rank-of-a-bst-node/
Number of smaller nodes than a node is equal to the size of the left subtree.
This leads us to assign rank to each of the node. Notice that
size(node) = size(node.left)+size(node.right)+1;
rank(node) = size(node.left)+1
public static TreeNode insert(final TreeNode root, final TreeNode node) { if (root == null || node == null) { return node; } TreeNode current = root; TreeNode parent = root; while (current != null) { if (current.key > node.key) { current.lcount++; current.size++; parent = current; current = current.left; } else { current.size++; parent = current; current = current.right; } } if (parent.key > node.key) { parent.left = node; } else { parent.right = node; } return root; } public static TreeNode kthSmallestElement(final TreeNode root, final int k) // select(k) { final int rank = root.lcount + 1; if (rank == k) { return root; } else if (rank > k) { return kthSmallestElement(root.left, k); } else { return kthSmallestElement(root.right, k - rank); } }Calculating rank during later phase
public static int OS_RANK(final TreeNode x) { int r = x.left.size + 1; TreeNode y = x; while (y.parent != null) { if (y.parent.right == y) { r += (y.parent.left != null ? y.parent.left.size : 0) + 1; } y = y.parent; } return r; }
http://www.geeksforgeeks.org/kth-smallest-element-in-bst-using-o1-extra-space/
Read full article from Find k-th smallest element in BST (Order Statistics in BST) | GeeksforGeeks
