Reconstructing a tree from depth information

Question

I have a data structure that describes a tree. Nodes are ordered, with "depth" information, and knowing the order and the depth the tree can be reconstructed. I'm not entirely sure how to describe it so I'm hoping this small example will illustrate it

node #1, depth 0 // parent: none
node #2, depth 1 // parent: #1
node #3, depth 1 // parent: #1
node #4, depth 2 // parent: #3
node #5, depth 1 // parent: #1
node #6, depth 2 // parent: #5

(I added parent information in there for clarification. That's not part of the data structure.)

I'm trying to write an algorithm (in JS, if that's any help) that will iterate over each node and build a tree out of the data. I'm fairly recursion is the way to go but beyond that I'm not sure where to start. Any suggestions?

Edit: The way I see it, I have four cases:

1. Node has depth 0 (initial case)
2. Node has same depth as previous
3. Node has greater depth as previous (should only be previous.depth+1)
4. Node has less depth than previous

Here's my pseudo-JS-code so far:

process (nodes, 0);
process = function(nodes, i) {
 cur = nodes[i], prev = nodes[i-1]
 if cur.depth = 0 then cur.parent = null // case #1
 else if cur.depth == prev.depth then cur.parent = prev.parent // case #2
 else if cur.depth > prev.depth then cur.parent = prev // case #3
 else // case #4... here's where I'm stuck.
 if i <= nodes.length then process (nodes, i+1)
}

• thorsten müller: Do you really want to store as "parent"? Having each node contain a list of child nodes would be more common and would make your job easier I think.
• Malcolm Crum: Oh... no, that was a case of me building code to fit my example I suppose. Storing an array of children would work just as fine I think - and be probably more useful down the line.
• thorsten müller: Any values to store in each node or can an empty node be just an empty array?
• Malcolm Crum: The nodes themselves have other data (they're actually posts on a threaded forum, so post time, post author, content, etc). The only data I'm adding here is tree structure info though.

Answer 1

It is quite simple. You need a FIFO container (stack) and root node.

Always add new nodes as childs of front node in stack. When you see greater depth than previous, put latest added note onto stack, before adding next. When you see smaller depth, pop from stack delta times (again: before adding next node). Don't track current depth, it is already tracked by stack.

Pseudocode:

root = new Node
stack = new Stack
stack.push(root)
for record in records
 delta = record.depth - (stack.size - 1)
 if delta > 0
 assert delta == 1
 stack.push(stack.front().last_child())
 while delta < 0
 stack.pop()
 delta++
 stack.front().add_child(record.node)
return root

You can understand it better, if you represent depth as N indents, where N = depth.

node #1, depth 0 // parent: none
 node #2, depth 1 // parent: #1
 node #3, depth 1 // parent: #1
 node #4, depth 2 // parent: #3
 node #5, depth 1 // parent: #1
 node #6, depth 2 // parent: #5

• Malcolm Crum: I think this leave us with root as a child of root after we process the first node, right?
• Malcolm Crum: And if I skip the first node in the for loop and start iterating with the first reply, I fail in the if statement after trying to access the last_child() of root: root has no children yet.
• Shadows In Rain: @Crummy Yes. If your data format guarantees than first record will be only root, you can extract it from container before passing it to loop. But then you need to offset record.depth by -1.
• Malcolm Crum: Thanks, this did the trick after a bit more poking around. For anyone else interested, here's a copy/paste of my final function: pastebin.com/cuw3WEGi

Answer 2

Ok, some pseudocode and ugly globals for enhanced lazyness:

var tree;
var position = 0;
var list = []; // to be filled with your list before you start;
process = function(depth, pos) {
 var nodes = [];
 while(list[pos + 1].depth >= depth) {
 pos = pos + 1;
 if(list[pos].depth == depth) {
 nodes.push({some_value: value, 
 another_value: whatever,
 children: null});
 else {
 nodes[nodes.length-1].children = process(depth + 1, pos);
 }
 };
 return nodes;
};
tree = process(0, 0);

So, I hope I didn't mess up too many details, but the idea should work.