blocks|key|1105185|text|对于二叉树，顺序遍历将返回元素...按顺序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105186|只需执行一次顺序遍历，并在遍历k个元素后停止。|1105187|对于k的常量，O(1)。|1105188|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

For a binary search tree, an inorder traversal will return elements ... in order.

Just do an inorder traversal and stop after traversing k elements.

O(1) for constant values of k.

blocks|key|1320158|text|给出一个简单的二叉树，你所能做的就是从最小的开始，然后向上遍历找到正确的节点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320159|如果要经常这样做，可以向每个节点添加一个属性，表示其左子树中有多少个节点。使用它，您可以直接将树下降到正确的节点。|1320160|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Given just a plain binary search tree, about all you can do is start from the smallest, and traverse upward to find the right node.

If you're going to do this very often, you can add an attribute to each node signifying how many nodes are in its left sub-tree. Using that, you can descend the tree directly to the correct node.

blocks|key|1105270|text|这就是我所想的，并且它是有效的。它将在o(log+)中运行|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105271|public+static+int+FindkThSmallestElemet(Node+root,+int+k)
++++{
++++++++int+count+=+0;
++++++++Node+current+=+root;

++++++++while+(current+!=+null)
++++++++{
++++++++++++count%2B%2B;
++++++++++++current+=+current.left;
++++++++}
++++++++current+=+root;

++++++++while+(current+!=+null)
++++++++{
++++++++++++if+(count+==+k)
++++++++++++++++return+current.data;
++++++++++++else
++++++++++++{
++++++++++++++++current+=+current.left;
++++++++++++++++count--;
++++++++++++}
++++++++}

++++++++return+-1;


++++}+//+end+of+function+FindkThSmallestElemet|code-block|syntax|javascript|1105272|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This is what I though and it works. It will run in o(log n ) 

<pre><code>public static int FindkThSmallestElemet(Node root, int k)
 {
 int count = 0;
 Node current = root;

 while (current != null)
 {
 count++;
 current = current.left;
 }
 current = root;

 while (current != null)
 {
 if (count == k)
 return current.data;
 else
 {
 current = current.left;
 count--;
 }
 }

 return -1;


 } // end of function FindkThSmallestElemet
</code></pre>

blocks|key|1320231|text|public+int+ReturnKthSmallestElement1(int+k)
++++{
++++++++Node+node+=+Root;

++++++++int+count+=+k;

++++++++int+sizeOfLeftSubtree+=+0;

++++++++while(node+!=+null)
++++++++{

++++++++++++sizeOfLeftSubtree+=+node.SizeOfLeftSubtree();

++++++++++++if+(sizeOfLeftSubtree+%2B+1+==+count)
++++++++++++++++return+node.Value;
++++++++++++else+if+(sizeOfLeftSubtree+<+count)
++++++++++++{
++++++++++++++++node+=+node.Right;
++++++++++++++++count+-=+sizeOfLeftSubtree%2B1;
++++++++++++}
++++++++++++else
++++++++++++{
++++++++++++++++node+=+node.Left;
++++++++++++}
++++++++}

++++++++return+-1;
++++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1320232|这是我基于上面的算法用C#实现的，我只是想把它贴出来，这样人们就可以更好地理解它对我的作用|unstyled|1320233|谢谢你，IVlad|1320234|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|L|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|F|7|N|8|@]|9|@]|A|$]]]|J|$]]

<pre><code>public int ReturnKthSmallestElement1(int k)
 {
 Node node = Root;

 int count = k;

 int sizeOfLeftSubtree = 0;

 while(node != null)
 {

 sizeOfLeftSubtree = node.SizeOfLeftSubtree();

 if (sizeOfLeftSubtree + 1 == count)
 return node.Value;
 else if (sizeOfLeftSubtree &lt; count)
 {
 node = node.Right;
 count -= sizeOfLeftSubtree+1;
 }
 else
 {
 node = node.Left;
 }
 }

 return -1;
 }
</code></pre>

this is my implementation in C# based on the algorithm above just thought I'd post it so people can understand better it works for me

thank you IVlad

blocks|key|1105343|text|这很有效:+status+:是保存是否找到元素的数组。K:是要找到的第k个元素。count+:跟踪遍历树过程中遍历的节点数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105344|int+kth(struct+tree*+node,+int*+status,+int+k,+int+count)
{
++++if+(!node)+return+count;
++++count+=+kth(node->lft,+status,+k,+count);++
++++if(+status[1]+)+return+status[0];
++++if+(count+==+k)+{+
++++++++status[0]+=+node->val;
++++++++status[1]+=+1;
++++++++return+status[0];
++++}
++++count+=+kth(node->rgt,+status,+k,+count%2B1);
++++if(+status[1]+)+return+status[0];
++++return+count;
}|code-block|syntax|javascript|1105345|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This works well: status : is the array which holds whether element is found. k : is kth element to be found. count : keeps track of number of nodes traversed during the tree traversal.

<pre><code>int kth(struct tree* node, int* status, int k, int count)
{
 if (!node) return count;
 count = kth(node-&gt;lft, status, k, count); 
 if( status[1] ) return status[0];
 if (count == k) { 
 status[0] = node-&gt;val;
 status[1] = 1;
 return status[0];
 }
 count = kth(node-&gt;rgt, status, k, count+1);
 if( status[1] ) return status[0];
 return count;
}
</code></pre>

blocks|key|1105351|text|这是我的两分钱..。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105352|int+numBSTnodes(const+Node*+pNode){
+++++if(pNode+==+NULL)+return+0;
+++++return+(numBSTnodes(pNode->left)%2BnumBSTnodes(pNode->right)%2B1);
}


//This+function+will+find+Kth+smallest+element
Node*+findKthSmallestBSTelement(Node*+root,+int+k){
+++++Node*+pTrav+=+root;
+++++while(k+>+0){
+++++++++int+numNodes+=+numBSTnodes(pTrav->left);
+++++++++if(numNodes+>=+k){
++++++++++++++pTrav+=+pTrav->left;
+++++++++}
+++++++++else{
++++++++++++++//subtract+left+tree+nodes+and+root+count+from+'k'
++++++++++++++k+-=+(numBSTnodes(pTrav->left)+%2B+1);
++++++++++++++if(k+==+0)+return+pTrav;
++++++++++++++pTrav+=+pTrav->right;
++++++++}

++++++++return+NULL;
+}|code-block|syntax|javascript|1105353|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Well here is my 2 cents...

<pre><code>int numBSTnodes(const Node* pNode){
 if(pNode == NULL) return 0;
 return (numBSTnodes(pNode-&gt;left)+numBSTnodes(pNode-&gt;right)+1);
}


//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
 Node* pTrav = root;
 while(k &gt; 0){
 int numNodes = numBSTnodes(pTrav-&gt;left);
 if(numNodes &gt;= k){
 pTrav = pTrav-&gt;left;
 }
 else{
 //subtract left tree nodes and root count from 'k'
 k -= (numBSTnodes(pTrav-&gt;left) + 1);
 if(k == 0) return pTrav;
 pTrav = pTrav-&gt;right;
 }

 return NULL;
 }
</code></pre>

blocks|key|1320326|text|一种更简单的解决方案是按顺序遍历并跟踪当前要打印的元素(不打印它)。当我们到达k时，打印元素并跳过树遍历的其余部分。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320327|void+findK(Node*+p,+int*+k)+{
++if(!p+%7C%7C+k+<+0)+return;
++findK(p->left,+k);
++--k;
++if(k+==+0)+{+
++++print+p->data;
++++return;++
++}+
++findK(p->right,+k);+
}|code-block|syntax|javascript|1320328|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed (without printing it). When we reach k, print the element and skip rest of tree traversal.

<pre><code>void findK(Node* p, int* k) {
 if(!p || k &lt; 0) return;
 findK(p-&gt;left, k);
 --k;
 if(k == 0) { 
 print p-&gt;data;
 return; 
 } 
 findK(p-&gt;right, k); 
}
</code></pre>

blocks|key|1105433|text|您可以使用迭代的中序遍历：http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal，并在将节点弹出堆栈之后对第k个元素进行简单的检查。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1105434|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal^0|D|1R|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You can use iterative inorder traversal:
<a href="http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal" rel="noreferrer">http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal</a>
with a simple check for kth element after poping a node out of the stack.

blocks|key|1320404|text|虽然这绝对不是问题的最佳解决方案，但这是另一个潜在的解决方案，我认为有些人可能会感兴趣：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320405|/**
+*+Treat+the+bst+as+a+sorted+list+in+descending+order+and+find+the+element+
+*+in+position+k.
+*
+*+Time+complexity+BigO+(+n%5E2+)
+*
+*+2n+%2B+sum(+1+*+n/2+%2B+2+*+n/4+%2B+...+(+2%5En-1)+*+n/n+)+=+
+*+2n+%2B+sigma+a=1+to+n+(+(2%5E(a-1))+*+n+/+2%5Ea+)+=+2n+%2B+n(n-1)/4
+*
+*+@param+t+The+root+of+the+binary+search+tree.
+*+@param+k+The+position+of+the+element+to+find.
+*+@return+The+value+of+the+element+at+position+k.
+*/
public+static+int+kElement2(+Node+t,+int+k+)+{
++++int+treeSize+=+sizeOfTree(+t+);

++++return+kElement2(+t,+k,+treeSize,+0+).intValue();
}

/**
+*+Find+the+value+at+position+k+in+the+bst+by+doing+an+in-order+traversal+
+*+of+the+tree+and+mapping+the+ascending+order+index+to+the+descending+order+
+*+index.
+*
+*
+*+@param+t+Root+of+the+bst+to+search+in.
+*+@param+k+Index+of+the+element+being+searched+for.
+*+@param+treeSize+Size+of+the+entire+bst.
+*+@param+count+The+number+of+node+already+visited.
+*+@return+Either+the+value+of+the+kth+node,+or+Double.POSITIVE_INFINITY+if+
+*+++++++++not+found+in+this+sub-tree.
+*/
private+static+Double+kElement2(+Node+t,+int+k,+int+treeSize,+int+count+)+{
++++//+Double.POSITIVE_INFINITY+is+a+marker+value+indicating+that+the+kth+
++++//+element+wasn't+found+in+this+sub-tree.
++++if+(+t+==+null+)
++++++++return+Double.POSITIVE_INFINITY;

++++Double+kea+=+kElement2(+t.getLeftSon(),+k,+treeSize,+count+);

++++if+(+kea+!=+Double.POSITIVE_INFINITY+)
++++++++return+kea;

++++//+The+index+of+the+current+node.
++++count+%2B=+1+%2B+sizeOfTree(+t.getLeftSon()+);

++++//+Given+any+index+from+the+ascending+in+order+traversal+of+the+bst,+
++++//+treeSize+%2B+1+-+index+gives+the
++++//+corresponding+index+in+the+descending+order+list.
++++if+(+(+treeSize+%2B+1+-+count+)+==+k+)
++++++++return+(double)t.getNumber();

++++return+kElement2(+t.getRightSon(),+k,+treeSize,+count+);
}|code-block|syntax|javascript|1320406|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

While this is definitely not the optimal solution to the problem, it is another potential solution which I thought some people might find interesting:

<pre><code>/**
 * Treat the bst as a sorted list in descending order and find the element 
 * in position k.
 *
 * Time complexity BigO ( n^2 )
 *
 * 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) = 
 * 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
 *
 * @param t The root of the binary search tree.
 * @param k The position of the element to find.
 * @return The value of the element at position k.
 */
public static int kElement2( Node t, int k ) {
 int treeSize = sizeOfTree( t );

 return kElement2( t, k, treeSize, 0 ).intValue();
}

/**
 * Find the value at position k in the bst by doing an in-order traversal 
 * of the tree and mapping the ascending order index to the descending order 
 * index.
 *
 *
 * @param t Root of the bst to search in.
 * @param k Index of the element being searched for.
 * @param treeSize Size of the entire bst.
 * @param count The number of node already visited.
 * @return Either the value of the kth node, or Double.POSITIVE_INFINITY if 
 * not found in this sub-tree.
 */
private static Double kElement2( Node t, int k, int treeSize, int count ) {
 // Double.POSITIVE_INFINITY is a marker value indicating that the kth 
 // element wasn't found in this sub-tree.
 if ( t == null )
 return Double.POSITIVE_INFINITY;

 Double kea = kElement2( t.getLeftSon(), k, treeSize, count );

 if ( kea != Double.POSITIVE_INFINITY )
 return kea;

 // The index of the current node.
 count += 1 + sizeOfTree( t.getLeftSon() );

 // Given any index from the ascending in order traversal of the bst, 
 // treeSize + 1 - index gives the
 // corresponding index in the descending order list.
 if ( ( treeSize + 1 - count ) == k )
 return (double)t.getNumber();

 return kElement2( t.getRightSon(), k, treeSize, count );
}
</code></pre>

blocks|key|1105487|text|我们可以简单地使用in+order遍历，并将访问过的元素推送到堆栈上。弹出k次，即可得到答案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105488|我们也可以在k个元素之后停止|1105489|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Well we can simply use the in order traversal and push the visited element onto a stack.
pop k number of times, to get the answer.

we can also stop after k elements

blocks|key|1320468|text|签名：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320469|Node+*+find(Node*+tree,+int+*n,+int+k);|code-block|syntax|javascript|1320470|调用方式：|1320471|*n+=+0;
kthNode+=+find(root,+n,+k);|1320472|定义：|1320473|Node+*+find+(+Node+*+tree,+int+*n,+int+k)
{
+++Node+*temp+=+NULL;

+++if+(tree->left+&&+*n<k)
++++++temp+=+find(tree->left,+n,+k);

+++*n%2B%2B;

+++if(*n==k)
++++++temp+=+root;

+++if+(tree->right+&&+*n<k)
++++++temp+=+find(tree->right,+n,+k);

+++return+temp;
}|1320474|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

signature:

<pre><code>Node * find(Node* tree, int *n, int k);
</code></pre>

call as:

<pre><code>*n = 0;
kthNode = find(root, n, k);
</code></pre>

definition:

<pre><code>Node * find ( Node * tree, int *n, int k)
{
 Node *temp = NULL;

 if (tree-&gt;left &amp;&amp; *n&lt;k)
 temp = find(tree-&gt;left, n, k);

 *n++;

 if(*n==k)
 temp = root;

 if (tree-&gt;right &amp;&amp; *n&lt;k)
 temp = find(tree-&gt;right, n, k);

 return temp;
}
</code></pre>

blocks|key|1320489|text|完整BST案例的解决方案:-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320490|Node+kSmallest(Node+root,+int+k)+{
++int+i+=+root.size();+//+2%5Eheight+-+1,+single+node+is+height+=+1;
++Node+result+=+root;
++while+(i+-+1+>+k)+{
++++i+=+(i-1)/2;++//+size+of+left+subtree
++++if+(k+<+i)+{
++++++result+=+result.left;
++++}+else+{
++++++result+=+result.right;
++++++k+-=+i;
++++}++
++}
++return+i-1==k+?+result:+null;
}|code-block|syntax|javascript|1320491|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Solution for complete BST case :-

<pre><code>Node kSmallest(Node root, int k) {
 int i = root.size(); // 2^height - 1, single node is height = 1;
 Node result = root;
 while (i - 1 &gt; k) {
 i = (i-1)/2; // size of left subtree
 if (k &lt; i) {
 result = result.left;
 } else {
 result = result.right;
 k -= i;
 } 
 }
 return i-1==k ? result: null;
}
</code></pre>

blocks|key|1105595|text|Linux内核有一个优秀的增强红黑树数据结构，它支持linux/lib/rbtree.c中O(log+)的基于等级的操作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105596|在http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java以及RbRoot.java和RbNode.java上也可以找到一个非常粗糙的Java端口。第n个元素可以通过调用RbNode.nth(RbNode节点，int+)来获得，传入树根。|offset|length|1105597|entityMap|0|LINK|mutability|MUTABLE|url|http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java^0|0|1|30|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

The Linux Kernel has an excellent augmented red-black tree data structure that supports rank-based operations in O(log n) in linux/lib/rbtree.c.

A very crude Java port can also be found at <a href="http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java" rel="nofollow">http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java</a>, together with RbRoot.java and RbNode.java. The n'th element can be obtained by calling RbNode.nth(RbNode node, int n), passing in the root of the tree.

blocks|key|1105672|text|我写了一个简洁的函数来计算第k个最小元素。我使用顺序遍历，并在到达第k个最小元素时停止。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105673|void+btree::kthSmallest(node*+temp,+int&+k){
if(+temp!=+NULL)+++{
+kthSmallest(temp->left,k);+++++++
+if(k+>0)
+{
+++++if(k==1)
++++{
++++++cout<<temp->value<<endl;
++++++return;
++++}

++++k--;
+}

+kthSmallest(temp->right,k);++}}|code-block|syntax|javascript|1105674|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

i wrote a neat function to calculate the kth smallest element. I uses in-order traversal and stops when the it reaches the kth smallest element. 

<pre><code>void btree::kthSmallest(node* temp, int&amp; k){
if( temp!= NULL) {
 kthSmallest(temp-&gt;left,k); 
 if(k &gt;0)
 {
 if(k==1)
 {
 cout&lt;&lt;temp-&gt;value&lt;&lt;endl;
 return;
 }

 k--;
 }

 kthSmallest(temp-&gt;right,k); }}
</code></pre>

blocks|key|1320709|text|http://www.geeksforgeeks.org/archives/10379|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1320710|这是这个问题的确切答案：|1320711|1.在O(n)时间内使用顺序遍历2.在k%2Blog+n时间内使用增广树|1320712|entityMap|0|LINK|mutability|MUTABLE|url^0|0|17|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@$A|P|B|Q|1|R]]|C|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|4]]]]

<a href="http://www.geeksforgeeks.org/archives/10379" rel="nofollow">http://www.geeksforgeeks.org/archives/10379</a>

this is the exact answer to this question:-

1.using inorder traversal on O(n) time
2.using Augmented tree in k+log n time

blocks|key|1320739|text|//添加不带递归的java版本|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320740|public+static+<T>+void+find(TreeNode<T>+node,+int+num){
++++Stack<TreeNode<T>>+stack+=+new+Stack<TreeNode<T>>();

++++TreeNode<T>+current+=+node;
++++int+tmp+=+num;

++++while(stack.size()+>+0+%7C%7C+current!=null){
++++++++if(current!=+null){
++++++++++++stack.add(current);
++++++++++++current+=+current.getLeft();
++++++++}else{
++++++++++++current+=+stack.pop();
++++++++++++tmp--;

++++++++++++if(tmp+==+0){
++++++++++++++++System.out.println(current.getValue());
++++++++++++++++return;
++++++++++++}

++++++++++++current+=+current.getRight();
++++++++}
++++}
}|code-block|syntax|javascript|1320741|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

//add a java version without recursion

<pre><code>public static &lt;T&gt; void find(TreeNode&lt;T&gt; node, int num){
 Stack&lt;TreeNode&lt;T&gt;&gt; stack = new Stack&lt;TreeNode&lt;T&gt;&gt;();

 TreeNode&lt;T&gt; current = node;
 int tmp = num;

 while(stack.size() &gt; 0 || current!=null){
 if(current!= null){
 stack.add(current);
 current = current.getLeft();
 }else{
 current = stack.pop();
 tmp--;

 if(tmp == 0){
 System.out.println(current.getValue());
 return;
 }

 current = current.getRight();
 }
 }
}
</code></pre>

blocks|key|1105771|text|int+RecPrintKSmallest(Node_ptr+head,int+k){
++if(head!=NULL){
++++k=RecPrintKSmallest(head->left,k);
++++if(k>0){
++++++printf("%25c+",head->Node_key.key);
++++++k--;
++++}
++++k=RecPrintKSmallest(head->right,k);
++}
++return+k;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1105772|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>int RecPrintKSmallest(Node_ptr head,int k){
 if(head!=NULL){
 k=RecPrintKSmallest(head-&gt;left,k);
 if(k&gt;0){
 printf("%c ",head-&gt;Node_key.key);
 k--;
 }
 k=RecPrintKSmallest(head-&gt;right,k);
 }
 return k;
}
</code></pre>

blocks|key|1105782|text|public+TreeNode+findKthElement(TreeNode+root,+int+k){
++++if((k==numberElement(root.left)%2B1)){
++++++++return+root;
++++}
++++else+if(k>numberElement(root.left)%2B1){
++++++++findKthElement(root.right,k-numberElement(root.left)-1);
++++}
++++else{
++++++++findKthElement(root.left,+k);
++++}
}

public+int+numberElement(TreeNode+node){
++++if(node==null){
++++++++return+0;
++++}
++++else{
++++++++return+numberElement(node.left)+%2B+numberElement(node.right)+%2B+1;
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1105783|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public TreeNode findKthElement(TreeNode root, int k){
 if((k==numberElement(root.left)+1)){
 return root;
 }
 else if(k&gt;numberElement(root.left)+1){
 findKthElement(root.right,k-numberElement(root.left)-1);
 }
 else{
 findKthElement(root.left, k);
 }
}

public int numberElement(TreeNode node){
 if(node==null){
 return 0;
 }
 else{
 return numberElement(node.left) + numberElement(node.right) + 1;
 }
}
</code></pre>

blocks|key|1320796|text|我找不到更好的algorithm..so，我决定写一个:)如果这是错误的，请纠正我。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320797|class+KthLargestBST{
protected+static+int+findKthSmallest(BSTNode+root,int+k){//user+calls+this+function
++++int+[]+result=findKthSmallest(root,k,0);//I+call+another+function+inside
++++return+result[1];
}
private+static+int[]+findKthSmallest(BSTNode+root,int+k,int+count){//returns+result[]2+array+containing+count+in+rval[0]+and+desired+element+in+rval[1]+position.
++++if(root==null){
++++++++int[]++i=new+int[2];
++++++++i[0]=-1;
++++++++i[1]=-1;
++++++++return+i;
++++}else{
++++++++int+rval[]=new+int[2];
++++++++int+temp[]=new+int[2];
++++++++rval=findKthSmallest(root.leftChild,k,count);
++++++++if(rval[0]!=-1){
++++++++++++count=rval[0];
++++++++}
++++++++count%2B%2B;
++++++++if(count==k){
++++++++++++rval[1]=root.data;
++++++++}
++++++++temp=findKthSmallest(root.rightChild,k,(count));
++++++++if(temp[0]!=-1){
++++++++++++count=temp[0];
++++++++}
++++++++if(temp[1]!=-1){
++++++++++++rval[1]=temp[1];
++++++++}
++++++++rval[0]=count;
++++++++return+rval;
++++}
}
public+static+void+main(String+args[]){
++++BinarySearchTree+bst=new+BinarySearchTree();
++++bst.insert(6);
++++bst.insert(8);
++++bst.insert(7);
++++bst.insert(4);
++++bst.insert(3);
++++bst.insert(4);
++++bst.insert(1);
++++bst.insert(12);
++++bst.insert(18);
++++bst.insert(15);
++++bst.insert(16);
++++bst.inOrderTraversal();
++++System.out.println();
++++System.out.println(findKthSmallest(bst.root,11));
}|code-block|syntax|javascript|1320798|}|1320799|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I couldn't find a better algorithm..so decided to write one :)
Correct me if this is wrong.

<pre><code>class KthLargestBST{
protected static int findKthSmallest(BSTNode root,int k){//user calls this function
 int [] result=findKthSmallest(root,k,0);//I call another function inside
 return result[1];
}
private static int[] findKthSmallest(BSTNode root,int k,int count){//returns result[]2 array containing count in rval[0] and desired element in rval[1] position.
 if(root==null){
 int[] i=new int[2];
 i[0]=-1;
 i[1]=-1;
 return i;
 }else{
 int rval[]=new int[2];
 int temp[]=new int[2];
 rval=findKthSmallest(root.leftChild,k,count);
 if(rval[0]!=-1){
 count=rval[0];
 }
 count++;
 if(count==k){
 rval[1]=root.data;
 }
 temp=findKthSmallest(root.rightChild,k,(count));
 if(temp[0]!=-1){
 count=temp[0];
 }
 if(temp[1]!=-1){
 rval[1]=temp[1];
 }
 rval[0]=count;
 return rval;
 }
}
public static void main(String args[]){
 BinarySearchTree bst=new BinarySearchTree();
 bst.insert(6);
 bst.insert(8);
 bst.insert(7);
 bst.insert(4);
 bst.insert(3);
 bst.insert(4);
 bst.insert(1);
 bst.insert(12);
 bst.insert(18);
 bst.insert(15);
 bst.insert(16);
 bst.inOrderTraversal();
 System.out.println();
 System.out.println(findKthSmallest(bst.root,11));
}
</code></pre>

}

blocks|key|1105842|text|这也是可行的。只需在树中使用maxNode调用函数|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105843|def+k_largest(self，node，k)：如果k<0:返回None|1105844|+++++if+k+==+0:+++++++++++++return+node+++++++++else:+++++++++++++k+-=1+++++++++++++return+self.k\_largest(self.predecessor(node),+k)|code-block|syntax|javascript|1105845|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

this would work too. just call the function with maxNode in the tree

def k_largest(self, node , k):
 if k &lt; 0 :
 return None 
 if k == 0:
 return node
 else:
 k -=1
 return self.k_largest(self.predecessor(node), k)

blocks|key|1320895|text|我认为这比接受的答案更好，因为它不需要修改原始树节点来存储它的子节点的数量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1320896|我们只需要使用顺序遍历从左到右计算最小的节点，一旦计数等于K就停止搜索。|1320897|private+static+int+count+=+0;
public+static+void+printKthSmallestNode(Node+node,+int+k){
++++if(node+==+null){
++++++++return;
++++}

++++if(+node.getLeftNode()+!=+null+){
++++++++printKthSmallestNode(node.getLeftNode(),+k);
++++}

++++count+%2B%2B+;
++++if(count+<=+k+)
++++++++System.out.println(node.getValue()+%2B+",+count="+%2B+count+%2B+",+k="+%2B+k);

++++if(count+<+k++&&+node.getRightNode()+!=+null)
++++++++printKthSmallestNode(node.getRightNode(),+k);
}|code-block|syntax|javascript|1320898|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I think this is better than the accepted answer because it doesn't need to modify the original tree node to store the number of it's children nodes.

We just need to use the in-order traversal to count the smallest node from the left to right, stop searching once the count equals to K.

<pre><code>private static int count = 0;
public static void printKthSmallestNode(Node node, int k){
 if(node == null){
 return;
 }

 if( node.getLeftNode() != null ){
 printKthSmallestNode(node.getLeftNode(), k);
 }

 count ++ ;
 if(count &lt;= k )
 System.out.println(node.getValue() + ", count=" + count + ", k=" + k);

 if(count &lt; k &amp;&amp; node.getRightNode() != null)
 printKthSmallestNode(node.getRightNode(), k);
}
</code></pre>

blocks|key|1320914|text|public+static+Node+kth(Node+n,+int+k){
++++Stack<Node>+s=new+Stack<Node>();
++++int+countPopped=0;
++++while(!s.isEmpty()%7C%7Cn!=null){
++++++if(n!=null){
++++++++s.push(n);
++++++++n=n.left;
++++++}else{
++++++++node=s.pop();
++++++++countPopped%2B%2B;
++++++++if(countPopped==k){
++++++++++++return+node;
++++++++}
++++++++node=node.right;

++++++}
++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1320915|}|unstyled|1320916|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>public static Node kth(Node n, int k){
 Stack&lt;Node&gt; s=new Stack&lt;Node&gt;();
 int countPopped=0;
 while(!s.isEmpty()||n!=null){
 if(n!=null){
 s.push(n);
 n=n.left;
 }else{
 node=s.pop();
 countPopped++;
 if(countPopped==k){
 return node;
 }
 node=node.right;

 }
 }
</code></pre>

}

blocks|key|1105929|text|一个更简单的解决方案是按顺序遍历，并用计数器k跟踪当前要打印的元素。当我们达到k时，打印该元素。运行时间为O(n)。请记住，函数返回类型不能为void，它必须在每次递归调用后返回其更新值k。一种更好的解决方案是在每个节点上增加一个具有排序位置值的BST。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105930|public+static+int+kthSmallest+(Node+pivot,+int+k){
++++if(pivot+==+null+)
++++++++return+k;+++
++++k+=+kthSmallest(pivot.left,+k);
++++k--;
++++if(k+==+0){
++++++++System.out.println(pivot.value);
++++}
++++k+=+kthSmallest(pivot.right,+k);
++++return+k;
}|code-block|syntax|javascript|1105931|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

A simpler solution would be to do an inorder traversal and keep track of the element currently to be printed with a counter k. When we reach k, print the element. The runtime is O(n). Remember the function return type can not be void, it has to return its updated value of k after each recursive call. A better solution to this would be an augmented BST with a sorted position value at each node.

<pre><code>public static int kthSmallest (Node pivot, int k){
 if(pivot == null )
 return k; 
 k = kthSmallest(pivot.left, k);
 k--;
 if(k == 0){
 System.out.println(pivot.value);
 }
 k = kthSmallest(pivot.right, k);
 return k;
}
</code></pre>

blocks|key|1105972|text|最好的方法已经是there.But，我想为它添加一个简单的代码|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1105973|int+kthsmallest(treenode+*q,int+k){
int+n+=+size(q->left)+%2B+1;
if(n==k){
++++return+q->val;
}
if(n+>+k){
++++return+kthsmallest(q->left,k);
}
if(n+<+k){
++++return+kthsmallest(q->right,k+-+n);
}|code-block|syntax|javascript|1105974|}|1105975|int+size(treenode+*q){
if(q==NULL){
++++return+0;
}
else{
++++return+(+size(q->left)+%2B+size(q->right)+%2B+1+);
}}|1105976|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Best approach is already there.But I'd like to add a simple Code for that

<pre><code>int kthsmallest(treenode *q,int k){
int n = size(q-&gt;left) + 1;
if(n==k){
 return q-&gt;val;
}
if(n &gt; k){
 return kthsmallest(q-&gt;left,k);
}
if(n &lt; k){
 return kthsmallest(q-&gt;right,k - n);
}
</code></pre>

}

<pre><code>int size(treenode *q){
if(q==NULL){
 return 0;
}
else{
 return ( size(q-&gt;left) + size(q-&gt;right) + 1 );
}}
</code></pre>

blocks|key|1106019|text|使用辅助结果类跟踪是否找到节点和当前k。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1106020|public+class+KthSmallestElementWithAux+{

public+int+kthsmallest(TreeNode+a,+int+k)+{
++++TreeNode+ans+=+kthsmallestRec(a,+k).node;
++++if+(ans+!=+null)+{
++++++++return+ans.val;
++++}+else+{
++++++++return+-1;
++++}
}

private+Result+kthsmallestRec(TreeNode+a,+int+k)+{
++++//Leaf+node,+do+nothing+and+return
++++if+(a+==+null)+{
++++++++return+new+Result(k,+null);
++++}

++++//Search+left+first
++++Result+leftSearch+=+kthsmallestRec(a.left,+k);

++++//We+are+done,+no+need+to+check+right.
++++if+(leftSearch.node+!=+null)+{
++++++++return+leftSearch;
++++}

++++//Consider+number+of+nodes+found+to+the+left
++++k+=+leftSearch.k;

++++//Check+if+current+root+is+the+solution+before+going+right
++++k--;
++++if+(k+==+0)+{
++++++++return+new+Result(k+-+1,+a);
++++}

++++//Check+right
++++Result+rightBalanced+=+kthsmallestRec(a.right,+k);

++++//Consider+all+nodes+found+to+the+right
++++k+=+rightBalanced.k;

++++if+(rightBalanced.node+!=+null)+{
++++++++return+rightBalanced;
++++}

++++//No+node+found,+recursion+will+continue+at+the+higher+level
++++return+new+Result(k,+null);

}

private+class+Result+{
++++private+final+int+k;
++++private+final+TreeNode+node;

++++Result(int+max,+TreeNode+node)+{
++++++++this.k+=+max;
++++++++this.node+=+node;
++++}
}
}|code-block|syntax|javascript|1106021|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Using auxiliary Result class to track if node is found and current k.

<pre><code>public class KthSmallestElementWithAux {

public int kthsmallest(TreeNode a, int k) {
 TreeNode ans = kthsmallestRec(a, k).node;
 if (ans != null) {
 return ans.val;
 } else {
 return -1;
 }
}

private Result kthsmallestRec(TreeNode a, int k) {
 //Leaf node, do nothing and return
 if (a == null) {
 return new Result(k, null);
 }

 //Search left first
 Result leftSearch = kthsmallestRec(a.left, k);

 //We are done, no need to check right.
 if (leftSearch.node != null) {
 return leftSearch;
 }

 //Consider number of nodes found to the left
 k = leftSearch.k;

 //Check if current root is the solution before going right
 k--;
 if (k == 0) {
 return new Result(k - 1, a);
 }

 //Check right
 Result rightBalanced = kthsmallestRec(a.right, k);

 //Consider all nodes found to the right
 k = rightBalanced.k;

 if (rightBalanced.node != null) {
 return rightBalanced;
 }

 //No node found, recursion will continue at the higher level
 return new Result(k, null);

}

private class Result {
 private final int k;
 private final TreeNode node;

 Result(int max, TreeNode node) {
 this.k = max;
 this.node = node;
 }
}
}
</code></pre>

blocks|key|1321094|text|+public+int+printInorder(Node+node,+int+k)+
++++{+
++++++++if+(node+==+null+%7C%7C+k+<=+0)+//Stop+traversing+once+you+found+the+k-th+smallest+element
++++++++++++return+k;+

++++++++/*+first+recur+on+left+child+*/
++++++++k+=+printInorder(node.left,+k);+

++++++++k--;
++++++++if(k+==+0)+{++
++++++++++++System.out.print(node.key);
++++++++}

++++++++/*+now+recur+on+right+child+*/
++++++++return+printInorder(node.right,+k);
++++}+|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1321095|这个java递归算法一旦找到第k个最小的元素就停止递归。|unstyled|1321096|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code> public int printInorder(Node node, int k) 
 { 
 if (node == null || k &lt;= 0) //Stop traversing once you found the k-th smallest element
 return k; 

 /* first recur on left child */
 k = printInorder(node.left, k); 

 k--;
 if(k == 0) { 
 System.out.print(node.key);
 }

 /* now recur on right child */
 return printInorder(node.right, k);
 } 
</code></pre>

This java recursive algorithm, stops the recursion once the k-th smallest element is found.

blocks|key|1321138|text|Python解决方案时间复杂度:+O(n)空间复杂度:+O(1)|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1321139|我的想法是使用Morris+Inorder+Traversal|offset|length|1321140|class+Solution(object):
def+inorderTraversal(self,+current+,+k+):
++++while(current+is+not+None):++++#This+Means+we+have+reached+Right+Most+Node+i.e+end+of+LDR+traversal

++++++++if(current.left+is+not+None):++#If+Left+Exists+traverse+Left+First
++++++++++++pre+=+current.left+++#Goal+is+to+find+the+node+which+will+be+just+before+the+current+node+i.e+predecessor+of+current+node,+let's+say+current+is+D+in+LDR+goal+is+to+find+L+here
++++++++++++while(pre.right+is+not+None+and+pre.right+!=+current+):+#Find+predecesor+here
++++++++++++++++pre+=+pre.right
++++++++++++if(pre.right+is+None):++#In+this+case+predecessor+is+found+,+now+link+this+predecessor+to+current+so+that+there+is+a+path+and+current+is+not+lost
++++++++++++++++pre.right+=+current
++++++++++++++++current+=+current.left
++++++++++++else:+++++++++++++++++++#This+means+we+have+traverse+all+nodes+left+to+current+so+in+LDR+traversal+of+L+is+done
++++++++++++++++k+-=+1
++++++++++++++++if(k+==+0):
++++++++++++++++++++return+current.val
++++++++++++++++pre.right+=+None+++++++#Remove+the+link+tree+restored+to+original+here+
++++++++++++++++current+=+current.right
++++++++else:+++++++++++++++#In+LDR++LD+traversal+is+done+move+to+R+
++++++++++++k+-=+1
++++++++++++if(k+==+0):
++++++++++++++++return+current.val
++++++++++++current+=+current.right

++++return+0

def+kthSmallest(self,+root,+k):
++++return+self.inorderTraversal(+root+,+k++)|code-block|syntax|javascript|1321141|entityMap|0|LINK|mutability|MUTABLE|url|https://www.youtube.com/watch?v=wGXB9OWhPTg^0|0|7|O|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@$D|U|E|V|1|W]]|A|$]]|$1|F|3|G|5|H|7|X|8|@]|9|@]|A|$I|J]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

Python Solution 
Time Complexity : O(n)
Space Complexity : O(1)

Idea is to use <a href="https://www.youtube.com/watch?v=wGXB9OWhPTg" rel="nofollow noreferrer">Morris Inorder Traversal</a> 

<pre><code>class Solution(object):
def inorderTraversal(self, current , k ):
 while(current is not None): #This Means we have reached Right Most Node i.e end of LDR traversal

 if(current.left is not None): #If Left Exists traverse Left First
 pre = current.left #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
 while(pre.right is not None and pre.right != current ): #Find predecesor here
 pre = pre.right
 if(pre.right is None): #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
 pre.right = current
 current = current.left
 else: #This means we have traverse all nodes left to current so in LDR traversal of L is done
 k -= 1
 if(k == 0):
 return current.val
 pre.right = None #Remove the link tree restored to original here 
 current = current.right
 else: #In LDR LD traversal is done move to R 
 k -= 1
 if(k == 0):
 return current.val
 current = current.right

 return 0

def kthSmallest(self, root, k):
 return self.inorderTraversal( root , k )
</code></pre>

blocks|key|1321152|text|public+int+kthSmallest(TreeNode+root,+int+k)+{
+++++
++++LinkedList<TreeNode>+stack+=+new+LinkedList<TreeNode>();

++++while+(true)+{
++++++while+(root+!=+null)+{
++++++++stack.push(root);
++++++++root+=+root.left;
++++++}
++++++root+=+stack.pop();
++++++k+=+k+-+1;
++++++if+(k+==+0)+return+root.val;
++++++root+=+root.right;
++++}

}+++++|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1321153|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public int kthSmallest(TreeNode root, int k) {
 
 LinkedList&lt;TreeNode&gt; stack = new LinkedList&lt;TreeNode&gt;();

 while (true) {
 while (root != null) {
 stack.push(root);
 root = root.left;
 }
 root = stack.pop();
 k = k - 1;
 if (k == 0) return root.val;
 root = root.right;
 }

} 
</code></pre>

I need to find the kth smallest element in the binary search tree without using any static/global variable. How to achieve it efficiently?
The solution that I have in my mind is doing the operation in O(n), the worst case since I am planning to do an inorder traversal of the entire tree. But deep down I feel that I am not using the BST property here. Is my assumptive solution correct or is there a better one available ?

Find kth smallest element in a binary search tree in Optimum way

数据结构

Python

Linux

Java

我需要在二进制搜索树中找到第k个最小的元素，而不使用任何静态/全局变量。如何有效地实现它？我脑海中的解决方案是在O(n)中进行操作，这是最坏的情况，因为我计划对整个树进行顺序遍历。但在内心深处，我觉得我并没有在这里使用BST属性。我的假设解决方案是否正确，或者是否有更好的解决方案？

问用最优方法求二分查找树的第k个最小元素
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用最优方法求二分查找树的第k个最小元素EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用最优方法求二分查找树的第k个最小元素
EN