StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Simple dfs can do it, we have a counter set to zero. Start from the root and in each iteration check the node value if is greater than x, then increase the counter and run algorithm for child nodes. When the counter is bigger or equal to k the algorithm will be finished, also if there is no node to check, algorithm returns false. The code is simple. The running time is O(k) because at most you will check k node and each iteration is O(1).</p> <p>The pseudo-code looks like follows.</p> <pre><code> void CheckNode(Node node,int k, int x, ref int counter) { if (node.value > x) { counter++; if (counter >= k) return; CheckNode(node.Left, k, x, ref counter); CheckNode(node.Right,k, x, ref counter); } } </code></pre> <p>use it:</p> <pre><code> counter = 0; CheckNode(root,index,val,counter ); if (counter >= index) return true; return false; </code></pre> <p>if node.value < x then all children values are smaller than x and there is no need to check.</p> <p>As @Eric Mickelsen mentioned in comments worst case running time is exactly 2k-1 (k>0) as follows.</p> <blockquote> <p>The number of nodes visited with values greater than x will be at most k. Each node visited with value less than x must be a child of a visited node with value greater than x. However, because every node visited except the root must have a parent with value greater than x, the number of nodes of value less than x visited must be at most ((k-1)*2)-(k-1) = k-1, since k-1 of the (k-1)*2 children have values greater than x. This means that we visit k nodes greater than x and k-1 less than x, which is 2k-1.</p> </blockquote>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload