4

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)
}
|improve this question
  • 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. – thorsten müller Oct 12 '13 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. – Crummy Oct 12 '13 at 6:43
  • Any values to store in each node or can an empty node be just an empty array? – thorsten müller Oct 12 '13 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. – Crummy Oct 12 '13 at 6:49
2

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
|improve this answer
  • I think this leave us with root as a child of root after we process the first node, right? – Crummy Oct 13 '13 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. – Crummy Oct 13 '13 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. – Shadows In Rain Oct 13 '13 at 8:27
  • 2
    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 – Crummy Oct 13 '13 at 19:46
1

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.

|improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.