# It's a denary tree

• A naive solution is pre-order traversal of the tree. We can do better by skipping over a sub-tree if the k is larger than the number of nodes in that sub-tree + current index.

Function count does the part of counting number of nodes in a sub-tree given prefix of number in lexicographical order.

``````public class Solution {
int index = 0;
int ans = 0;
public int findKthNumber(int n, int k) {
for(int i=1;i<=9;i++) {
int c = count(n, i, "");
if(k>c+index) {
index+=c;
continue;
}
if(helper(n, k, ""+i)) break;
}
return ans;
}
public boolean helper(int n, int k, String cur) {
index++;
if(index==k) {
ans = Integer.valueOf(cur);
return true;
}
for(int i=0; i<=9; i++) {
int c = count(n, i, cur);
if(k>c+index) {
index+=c;
continue;
}
if(Integer.valueOf(cur+i)<=n) if(helper(n, k, cur+i)) return true;
}
return false;
}
public int count(int n, int i, String prefix) {
long cur = Long.valueOf(prefix+i);
int ans = 0;
int number = 1;
while(cur<=n) {
ans += number;
cur *= 10;
number *= 10;
}
if(n<(cur/10+number/10-1)) ans -= cur/10+number/10-1-n;
return ans;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.