# Reconstructing a tree from depth information

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)
}
``````
• 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. Commented Oct 12, 2013 at 6:41
• 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. Commented Oct 12, 2013 at 6:43
• Any values to store in each node or can an empty node be just an empty array? Commented Oct 12, 2013 at 6:47
• 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. Commented Oct 12, 2013 at 6:49

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++

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
``````
• I think this leave us with root as a child of root after we process the first node, right? Commented Oct 13, 2013 at 0:40
• 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. Commented Oct 13, 2013 at 0:41
• @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`. Commented Oct 13, 2013 at 8:27
• 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 Commented Oct 13, 2013 at 19:46

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.