I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like:
2210200200
for a tree like this
Using the reasoning of stack traversing, it is easy to show that a sequence can represent a tree structure iff all the sums of the k-first elements are bigger than k-1 when k is smaller than the length of the tree and that the sum of all elements of the tree is exactly the length of the tree minus 1. For example, the corresponding sums of 2210200200 are:
first k-sums : 2-4-5-5-7-7-7-9-9-9
while k-1 = 0-1-2-3-4-5-6-7-8-9
and the differences are:
2-3-3-2-3-2-1-2-1-0
My question is : for a fixed positive integer p>2, are there some simple critera to know if the p-nary notation of an integer can represent a tree? (simpler than developing the p-nary notations all the time?)
For example, for p=3, the integer 673824 is good because its ternary notation is 2210200200, and 673825 is not good because its ternary notation is 2210200201. And I would like to have an algo that returns the good ones between say 1000 and 10000000.