# Recursive TreeStore problem

**URL:** <https://www.ruby-forum.com/t/recursive-treestore-problem/162562>\
**Category:** Ruby-Gnome 2\
**Created:** [March 11, 2009, 12:55pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562 "2009-03-11T12:55:45Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 12:55pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/1 "2009-03-11T12:55:45Z")

</div>

I’ve built this recursive bit of code to take an array of arrays and  
create a treestore from it. It seems to do what it supposed to do  
except, child nodes are not appended to parent nodes. I suspect it has  
something to do with passing the “new” (treestore.append()) value. Any  
help would be appreciated.

def add\_nodes(treestore, parent\_id, parent)  
0.upto(@gallerybox.length-1) do |i|  
if t.to\_i == parent\_id  
new = treestore.append(parent)  
new[0] = @gallerybox[i][0].to\_i  
new[1] = @gallerybox[i][1].to\_i  
new[2] = @gallerybox[i][2]  
new[3] = @gallerybox[i][3]  
add\_nodes(treestore, @gallerybox[i][0], new)  
puts “new node done”  
end  
end  
end

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 4:25pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/2 "2009-03-11T16:25:38Z")

</div>

Ok, I’m an idiot. Trying to make something simple hard…Here’s the  
solution :

def populate\_tree(node, parentid)  
@gallerybox.each { |gallery|  
id=gallery[0].to\_i  
parent=gallery[1].to\_i  
name=gallery[2]  
created = gallery[3]  
if parent == parentid  
child=@treestore.append(node)  
child[0] = id  
child[1] = parent  
child[2] = name  
child[3] = created  
populate\_tree(child, id)  
end  
}  
end

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 5:28pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/3 "2009-03-11T17:28:09Z")

</div>

Miles K. wrote:

> Ok, I’m an idiot. Trying to make something simple hard…Here’s the  
> solution :
> 
> def populate\_tree(node, parentid)  
> @gallerybox.each { |gallery|  
> id=gallery[0].to\_i  
> parent=gallery[1].to\_i  
> name=gallery[2]  
> created = gallery[3]  
> if parent == parentid  
> [child=@treestore.append](mailto:child=@treestore.append)(node)  
> child[0] = id  
> child[1] = parent  
> child[2] = name  
> child[3] = created  
> populate\_tree(child, id)  
> end  
> }  
> end

Though your {{ if parent == parentid }} looks problematic, assuming it  
would, when fixed identify parent nodes properly, unless you have  
created parents elsewhere, I suggest you do the following:

def populate\_tree(node, parentid)  
@gallerybox.each do |gallery|  
if parent == parentid  
[child=@treestore.append](mailto:child=@treestore.append)(nil)  
child[0] = gallery[0].to\_i  
child[1] = gallery[1].to\_i  
child[2] = gallery[2]  
child[3] = gallery[3]  
populate\_tree(child, id)  
else  
[child=@treestore.append](mailto:child=@treestore.append)(node)  
child[0] = gallery[0].to\_i  
child[1] = gallery[1].to\_i  
child[2] = gallery[2]  
child[3] = gallery[3]  
populate\_tree(child, id)  
end  
end  
end

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:21pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/4 "2009-03-11T18:21:12Z")

</div>

Sorry for repeating my post but this is more eligible and better reveals  
some issues earlier hidden:

def populate\_tree(node, parentid)  
@gallerybox.each do |gallery|  
if parent\_identification == parentid  
parent = @treestore.append(nil)  
parent[0] = gallery[0].to\_i  
parent[1] = gallery[1].to\_i  
parent[2] = gallery[2]  
parent[3] = gallery[3]  
populate\_tree(parent, id)  
else  
child = @treestore.append(node)  
child[0] = gallery[0].to\_i  
child[1] = gallery[1].to\_i  
child[2] = gallery[2]  
child[3] = gallery[3]  
populate\_tree(child, id)  
end  
end  
end

However, I still do have an issue with {{ if parent\_identification ==  
parentid }}. I have tested this recursive method in a full-blown  
Ruby/Gtk GUI application and it works fine.

Cheers, Igor

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:09pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/5 "2009-03-11T18:09:03Z")

</div>

Igor P. wrote:

> Though your {{ if parent == parentid }} looks problematic, assuming it  
> would, when fixed identify parent nodes properly, unless you have  
> created parents elsewhere, I suggest you do the following:
> 
> def populate\_tree(node, parentid)  
> @gallerybox.each do |gallery|  
> if parent == parentid  
> [child=@treestore.append](mailto:child=@treestore.append)(nil)  
> child[0] = gallery[0].to\_i  
> child[1] = gallery[1].to\_i  
> child[2] = gallery[2]  
> child[3] = gallery[3]  
> populate\_tree(child, id)  
> else  
> [child=@treestore.append](mailto:child=@treestore.append)(node)  
> child[0] = gallery[0].to\_i  
> child[1] = gallery[1].to\_i  
> child[2] = gallery[2]  
> child[3] = gallery[3]  
> populate\_tree(child, id)  
> end  
> end  
> end

I have a mysql table like :

key\_id  
parent\_id  
data  
created

gallerybox is an array of rows of this table.

parent in the code refers to parent\_id from this table  
and parentid is the key\_id.

Initially I pass ( 0,nil ) to this function so that the inital pass  
builds the root level of the tree, the recursive builds all lower  
levels.

Perhaps my variable naming is poor but I think the original method  
works.

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:25pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/6 "2009-03-11T18:25:47Z")

</div>

> ```
> child=@treestore.append(node)
> child[0] = gallery[0].to_i
> child[1] = gallery[1].to_i
> child[2] = gallery[2]
> child[3] = gallery[3]
> populate_tree(child, id)
> end
> 
> ```
> 
> end  
> end

Any reason to duplicate so much code? I routinely hurt my eyes,  
nowadays..

def populate\_tree(node, parentid)  
@gallerybox.each do |gallery|  
[child=@treestore.append](mailto:child=@treestore.append)(parent == parentid ? nil : node)  
child[0] = gallery[0].to\_i  
child[1] = gallery[1].to\_i  
child[2] = gallery[2]  
child[3] = gallery[3]  
populate\_tree(child, id)  
end  
end

–  
Guillaume C. - [NVC Communication Obstacles Game](http://zarb.org/~gc/)

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:29pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/7 "2009-03-11T18:29:21Z")

</div>

Miles K. wrote:

> Initially I pass ( 0,nil ) to this function so that the inital pass  
> builds the root level of the tree, the recursive builds all lower  
> levels.

You may have multiple root levels each with its own children. Look at  
the example in Ruby/Gtk tutorial at  
[http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees](http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees), where  
“Cleaning supplies” and “Food” rows represent root levels. In fact I  
have tested your recursive method in this application.

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:31pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/8 "2009-03-11T18:31:04Z")

</div>

Guillaume C. wrote:

> Any reason to duplicate so much code? I routinely hurt my eyes,  
> nowadays..
> 
> def populate\_tree(node, parentid)  
> @gallerybox.each do |gallery|  
> [child=@treestore.append](mailto:child=@treestore.append)(parent == parentid ? nil : node)  
> child[0] = gallery[0].to\_i  
> child[1] = gallery[1].to\_i  
> child[2] = gallery[2]  
> child[3] = gallery[3]  
> populate\_tree(child, id)  
> end  
> end

True enough. I should have cleaned that up a bit. Verbosity sometimes  
helps me think through things.

Cheers.

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 6:34pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/9 "2009-03-11T18:34:39Z")

</div>

Igor P. wrote:

> Look at the example in Ruby/Gtk tutorial at  
> [http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees](http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees), where  
> “Cleaning supplies” and “Food” rows represent root levels. In fact I  
> have tested your recursive method in this application.

Comma, at the end of the link should be avoided, so try this:  
[http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees](http://ruby-gnome2.sourceforge.jp/hiki.cgi?tut-gtk2-treev-trees)

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 9:00pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/10 "2009-03-11T21:00:41Z")

</div>

Miles K. wrote:

> def populate\_tree(node, parentid)  
> @gallerybox.each do |gallery|  
> [child=@treestore.append](mailto:child=@treestore.append)(parent == parentid ? nil : node)  
> child[0] = gallery[0].to\_i  
> child[1] = gallery[1].to\_i  
> child[2] = gallery[2]  
> child[3] = gallery[3]  
> populate\_tree(child, id)  
> end  
> end

I was so excited about your “recursive invention” that I wanted to  
publish it on Ruby/Gtk2 tutorial web page, and in the process of doing  
so I discovered I was not really testing the recursive call with your  
populate\_tree, which is in fact wrong, because the way you wrote it  
makes it an infinite, never-ending recursion. I actually tested the  
following strategy:

def populate\_tree(parent, parentid)  
@gallerybox.each do |gallery|  
if parent\_identification == parentid  
parent = @treestore.append(nil)  
parent[0] = gallery[0].to\_i  
parent[1] = gallery[1].to\_i  
parent[2] = gallery[2]  
parent[3] = gallery[3]  
else  
child = @treestore.append(parent)  
child[0] = gallery[0].to\_i  
child[1] = gallery[1].to\_i  
child[2] = gallery[2]  
child[3] = gallery[3]  
end  
end  
end

I do believe your code would not work properly even if you take the  
recursive call out. You have to retain the value of the last iterator  
value across the block iterations and you are loosing that by creating a  
block local variable “child”. You need to either use method’s parameter  
like in my example (parent), or you need to define {{ parent = child =  
nil }} before entering the block.

And most importantly, your “shortened” or as you say “cleaned-up”  
version will also not work properly with multiple root rows, because you  
are overriding parent iterators by child iterators. Iterators are  
references and by doing what you are doing, you make them point to the  
same data items.

I do not exactly know how the internals of Gtk::TreeStore work here,  
but clearly we have something like the following problem with references  
and multi-dimensional arrays:

±---------------------------+  
| line = %w[. . . . .] |  
| page = [line, line, line] |  
| puts page.to\_s |  
| page[2][3] = 9 |  
| line[1] = “X” |  
| puts page.to\_s |  
±---------------------------+  
OUTPUT:  
…  
.X.9..X.9..X.9.

Again, sorry for my part of the slip.

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 11, 2009, 9:48pm UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/11 "2009-03-11T21:48:28Z")

</div>

Hi Igor,

The recursive function does work given my data set. The mysql table  
that I am drawing from already contains the parent/child relationships.

Table :

[INDEX] [PARENT] [DATA]  
1 0 food \>\> ROOT Category  
2 1 cheeses \>\> Sub-Category  
3 2 cheddar \>\> Item 1  
4 2 brie \>\> Item 2  
5 0 beverages \>\> ROOT Category

and so forth.

Does this clear it up at all?

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 12, 2009, 2:35am UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/12 "2009-03-12T02:35:49Z")

</div>

Miles K. wrote:

> The recursive function does work given my data set. The mysql table  
> that I am drawing from already contains the parent/child relationships.
> 
> Table :
> 
> [INDEX] [PARENT] [DATA]  
> 1 0 food \>\> ROOT Category  
> 2 1 cheeses \>\> Sub-Category  
> 3 2 cheddar \>\> Item 1  
> 4 2 brie \>\> Item 2  
> 5 0 beverages \>\> ROOT Category
> 
> and so forth.
> 
> Does this clear it up at all?

Hi Miles,

After what you have said now it does look that recursion is the best  
strategy to solve this algorithm. However you are growing it on me  
gradually. First you didn’t even consider multiple root records, and  
from your last post it is clear that you have not only multiple root  
records but multiple levels of indentation, i.e. not only  
two-dimensional Gtk::TreeStore structure but a multi-dimensional one.

And so I come back to my very first objection, which is your condition  
that when looked at superficially seemed to only determine the root  
nodes, but is actually the controlling mechanism for the recursion. You  
should have given more precise definition of what was only a  
hypothetical pseudo-code like condition “if t.to\_i == parent\_id”.

The second issue you have here is the problem which I have already  
covered extensively, and would show up only when you actually run a GUI  
application, where you would either get root and children nodes properly  
indented, or you would only get a two-dimensional layout!

Third minor problem which, indeed, can be programmatically accounted  
for, is with your list notation. Your [INDEX] [PARENT] [DATA]  
should actually look something like the following:

[INDEX] [PARENT] [DATA]  
0, 0, “food” \>\> ROOT Category  
1, 1, “cheeses” \>\> Sub-Category  
2, 1, “cheddar” \>\> Item 1  
3, 1, “brie” \>\> Item 1  
4, 4, “beverages” \>\> ROOT Category  
5, 5, “non-alcohol” \>\> Sub-Category  
6, 5, “pepsi” \>\> Item 1  
7, 5, “coke” \>\> Item 1  
8, 4, “alcoholic” \>\> Sub-Category  
9, 8, “wine” \>\> Item 1  
10, 8, “brandy” \>\> Item 1

I am really interested to see how you actually handled the problematic  
recursion terminating condition.

Cheers, Igor

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 12, 2009, 3:14am UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/13 "2009-03-12T03:14:23Z")

</div>

Igor P. wrote:

> Ooops, that’ll do:
> 
> [INDEX] [PARENT] [DATA]  
> 0, 0, “food” \>\> ROOT Category  
> 1, 0, “cheeses” \>\> Sub-Category  
> 2, 1, “cheddar” \>\> Item 1  
> 3, 1, “brie” \>\> Item 2  
> 4, 4, “beverages” \>\> ROOT Category  
> 5, 4, “non-alcohol” \>\> Sub-Category  
> 6, 5, “pepsi” \>\> Item 1  
> 7, 5, “coke” \>\> Item 2  
> 8, 4, “alcoholic” \>\> Sub-Category  
> 9, 8, “wine” \>\> Item 1  
> 10, 8, “brandy” \>\> Item 2

Hey Igor,

I think I get where you’re coming from now. Let me see if we can’t  
straighten this out.

The list notation is purely illustrative and represented the way my data  
is stored. It is important to note that the data is derived from a  
mysql table. The index is a self incrementing value that is generated  
by mysql as the key for the table. It will never begin at zero. If it  
were however, you are correct that it would endlessly repeat.

That being said, the above data set should be modified to reflect these  
two changes.

1. [Index] needs to start at 1 and increment from there.
2. the parent of “beverages” cannot be itself in order to be a Root  
Category. The parent of beverages would need to be 0.

Other than that, it would work fine.

–Miles

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 12, 2009, 10:13am UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/14 "2009-03-12T10:13:01Z")

</div>

Miles K. wrote:

> I think I get where you’re coming from now. Let me see if we can’t  
> straighten this out.
> 
> The list notation is purely illustrative and represented the way my data  
> is stored. It is important to note that the data is derived from a  
> mysql table. The index is a self incrementing value that is generated  
> by mysql as the key for the table. It will never begin at zero. If it  
> were however, you are correct that it would endlessly repeat.
> 
> That being said, the above data set should be modified to reflect these  
> two changes.
> 
> 1. [Index] needs to start at 1 and increment from there.
> 2. the parent of “beverages” cannot be itself in order to be a Root  
> Category. The parent of beverages would need to be 0.
> 
> Other than that, it would work fine.

Hi Miles,

I agree, with your last and second point, namely root for beverages  
should be 0 (I made a hasty mistake there), but I do not entirely agree  
with your first point though it is not a fatal problem and can be  
accommodated in a programmatic way. Strictly speaking index does start  
with zero and is logically the top root node, in fact, that is why you  
start your recursion with the nil parameter for the first node or  
iteration.

It was fun talking to you!  
Igor

---

<div class="post-metadata">

**Author:** ![taintedsushi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/ee59a6/32.png) [@taintedsushi](https://www.ruby-forum.com/u/taintedsushi)\
**Post date:** [March 12, 2009, 2:39am UTC](https://www.ruby-forum.com/t/recursive-treestore-problem/162562/15 "2009-03-12T02:39:43Z")

</div>

Ooops, that’ll do:

[INDEX] [PARENT] [DATA]  
0, 0, “food” \>\> ROOT Category  
1, 0, “cheeses” \>\> Sub-Category  
2, 1, “cheddar” \>\> Item 1  
3, 1, “brie” \>\> Item 2  
4, 4, “beverages” \>\> ROOT Category  
5, 4, “non-alcohol” \>\> Sub-Category  
6, 5, “pepsi” \>\> Item 1  
7, 5, “coke” \>\> Item 2  
8, 4, “alcoholic” \>\> Sub-Category  
9, 8, “wine” \>\> Item 1  
10, 8, “brandy” \>\> Item 2
