Hi, since the worst case is traversal the whole tree, so can we say the O(n), n is the number of the node we have in the tree. please correct me if I'm wrong.

Great solution. Thanks a lot. Actually, stack is not necessary. One variable is enough.

class Solution {
public:
int findKthNumber(int n, int k) {
int cur = 1;
while(k > 0) {
if(1 == k) return cur;
int sum = calc(n, cur);
if(k > sum) {
k -= sum;
cur = cur + 1;
}
else {
k --;
cur = cur * 10;
}
}
return cur;
}
int calc(int n, int64_t x) {
int ans = 0, t = 1;
while(x <= n) {
if(x + t - 1 <= n) ans += t;
else ans += n - x + 1;
x *= 10;
t *= 10;
}
return ans;
}
};

@weihanzh No problem. I was trying to do the pre-order traversal of Trie because I have seen a very similar problem which asks to print all values lexicographically smaller than a given target. But that problem is asking for a stronger output than this problem, so more expensive in time complexity. It is like the "log" fashion of binary search: if only asking for some value in a sorted array, should be able to do in O(log N)time; but if asking for printing all values smaller than a target value, then have to do in O(N) time.