Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# tree datastructure algorithm

Dorothy Taylor
Ranch Hand
Posts: 104
Hi

Can anyone suggest the code/logic for converting an n-ary tree to array and back?

Thanks

Jeff Verdegan
Bartender
Posts: 6109
6
tree ⇒ array: Presumably there is at least one method for walking the tree. Walk it, and at each node copy that value to the array.

array ⇒ tree: Presumably there is a method for adding a node to the tree. Iterate over the array, calling that method at each element.

dennis deems
Ranch Hand
Posts: 808
• 1
Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with. If I know I have a binary tree, then I can store the values of each node in an array tier by tier, but I have to leave empty cells wherever a node has fewer than two children. And I have to be extremely careful about the order in which I do this. Any way I look at it, I can't see how walking the tree would work at all.

Jeff Verdegan
Bartender
Posts: 6109
6
Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

That depends on the nature of the tree. Since the question is quite vague, with no details about the tree other than that it is n-ary, it's impossible to be very specific. If the tree behaves like a List, where iteration order matches insertion order, or if the tree behaves like a SortedSet, where iteration order follows sorting rules, then you'll get back what you started with. If neither of these are true, then it's impossible to do what the OP asks without more details about how elements will be added to and iterated over in the specific tree in question.

Winston Gutkowski
Bartender
Posts: 10527
64
Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

It might well not, and that may indeed be what you want.

For example, I could imagine a balancing method that went something like (pseudo-ish):

Although, as Jeff says, it's difficult to tell much from OP's description exactly what the requirements are.

Winston

dennis deems
Ranch Hand
Posts: 808
Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

Winston Gutkowski wrote:It might well not, and that may indeed be what you want.

If I don't care what the result is, I'm not sure why I need an algorithm.

Jeff Verdegan
Bartender
Posts: 6109
6
Dennis Deems wrote:
Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

Winston Gutkowski wrote:It might well not, and that may indeed be what you want.

If I don't care what the result is, I'm not sure why I need an algorithm.

I think it all just goes back to trying to take a broad swipe at a very vague question.

Dorothy Taylor
Ranch Hand
Posts: 104
If it was as simple as Jeff's solution suggests, I wouldn't have posted in this forum. So obviously the problem is convert the n-ary tree to an array. So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear, however, it will leave some empty values in the array. Hence this solution is not space efficient. Again, suppose we devise a space efficient algorithm in which there are no empty array elements. then how do we get back the tree from this array? Moreover the algorithm has to be generic i.e. n-ary. This means that the 'n' is also an input.

So my question is that is Jeff's solution the best that can be done in this case, or is there a better way out?

Dorothy Taylor
Ranch Hand
Posts: 104
Jeff Verdegan wrote:
Dennis Deems wrote:Jeff, it is unclear to me how, using your method, converting the array to a tree will result in the same tree structure I started with.

That depends on the nature of the tree. Since the question is quite vague, with no details about the tree other than that it is n-ary, it's impossible to be very specific.
If the tree behaves like a List, where iteration order matches insertion order, or if the tree behaves like a SortedSet, where iteration order follows sorting rules, then you'll get back what you started with. If neither of these are true, then it's impossible to do what the OP asks without more details about how elements will be added to and iterated over in the specific tree in question.

Since there are no specific things given other than it is an n-ary tree, one is free to make assumptions. However, for a binary or n-ary tree, I do not understand why the tree behaviour should be like a list or sorted set. A tree is a tree that can be traversed using breadth first or depth first traversals. We are not going to choose any elements from the tree on weightages etc. and create an array. Obviously we have to make use of tree properties only when only that is given to us.

Winston Gutkowski
Bartender
Posts: 10527
64
Dorothy Taylor wrote:So obviously the problem is convert the n-ary tree to an array. So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear,

Actually not. In a proper n-ary tree, the left child will be something like p(n^L)+1, where L is the level and p is the 'position' of the parent node in its level; and even then the formula only holds if the tree is perfectly balanced. The case you are quoting is for a heap, which is a special case of a binary tree.

however, it will leave some empty values in the array. Hence this solution is not space efficient.

Actually, if n is large enough, the space taken up by unused slots is very small. SkipLists, for example, use a stack of 'fast-track' pointers akin to your tree to access the elements in a linked list, and the main space inefficiency is in the linked list itself. If n=8, the total overhead for storing the pointers for x nodes in a well-balanced tree approaches x/7, whereas for the linked list itself, it's x (or 2x if the LL is bi-directional).

So my question is that is Jeff's solution the best that can be done in this case, or is there a better way out?

You might want to have a look at skiplists. Java's implementation is as a ConcurrentSkipListMap or Set, which are heavily skewed for concurrent operation, but the docs have references to William Pugh's paper, which shows you how to write your own.

Winston

Jeff Verdegan
Bartender
Posts: 6109
6
Dorothy Taylor wrote:If it was as simple as Jeff's solution suggests, I wouldn't have posted in this forum. So obviously the problem is convert the n-ary tree to an array.

I guess I was making some assumptions and oversimplifying the problem. Although a bit more detail in the original question would have helped.

So if the root node is n, then left child is 2n+1 and right is 2n+2. That is clear, however, it will leave some empty values in the array. Hence this solution is not space efficient.

Ah, now we're getting somewhere.

So you want to keep track of holes in the tree, but you want to consume zero memory to do so?

Again, suppose we devise a space efficient algorithm in which there are no empty array elements. then how do we get back the tree from this array?

In other words, "If I remove information, how do I get it back?" You don't.

Now, depending on the nature of the pattern of nodes and holes, you might be able to make use of some sort of compression. For instance, keep a separate array for runs of consecutive holes. If you have more than 4 consecutive holes in the main array, add indications for their start and end in the hole array.

Are you really dealing with such a huge amount of data with so many holes that it's really worth it though?

Have you actually tried it the simplest, most straightforward way and measured that it will waste an unacceptable amount of memory? Or are you just assuming and prematurely optimizing?