# Managing Hierarchical Tree-Like Data

**URL:** <https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554>\
**Category:** Ruby\
**Created:** [November 7, 2006, 10:47am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554 "2006-11-07T10:47:54Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:47am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/1 "2006-11-07T10:47:54Z")

</div>

Team:  
I’m looking for a pragmatic way of creating a tree from a list of  
items without knowing the depth of each.

For example:

max\_depth = 4 #considers each unique item below the depth of 4 to be one  
item\_tree = {}  
[“CarRedFast”,  
“CarGreenSlow”,  
“Car”,  
“CarRedFastAgileSadCheeseBurger”,  
“CarRedFastAgileHappyJoy”,  
“GreenApplePie”,  
“GreenApple”  
].each do |i|  
items = i.gsub(/[A-Z][a-z]/) {|i| “_" + i}.gsub(/^_/,  
“”).split(”\_")  
end

This builds an array from items based on the case but many times, I  
have needed to display this data in tree form as such:

#############################

# Desired output:

```
        Car(2)
                    Red(1)
                                Fast(1)
                                            Agile(2)
                                                        HappyJoy
                                                        SadCheeseBurger
                    Green(1)
                                Slow(0)
        Green(1)
                    Apple(1)
                                Pie(0)

```

###############################

I’ve come across this numerous times and am pretty sure there’s a  
better way of doing it.

This is pretty much what I have now and it feels SO wrong to write!

#This just feels horrible writing  
item\_tree = {}  
[“CarRedFast”,  
“CarGreenSlow”,  
“Car”,  
“CarRedFastAgileSadCheeseBurger”,  
“CarRedFastAgileHappyJoy”,  
“GreenApplePie”,  
“GreenApple”  
].each do |i|  
items = i.gsub(/[A-Z][a-z]/) {|i| “_" + i}.gsub(/^_/,  
“”).split(”\_")  
items.each do |item|  
if item\_tree.include? item[0]  
if item\_tree[item[0]].include? item[1]  
#yadadada  
else  
item\_tree[item[0]][item[1]] = {}  
end  
else  
item\_tree[item[0]] = {}  
end  
end  
end

Please… Any suggestions at all… All comments welcome!! TIA

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:48am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/2 "2006-11-07T10:48:00Z")

</div>

x1 wrote:

> Team:  
> I’m looking for a pragmatic way of creating a tree from a list of  
> items without knowing the depth of each.

How about this:  
class Hash  
def as\_tree( depth=0 )  
map{ |k,subtree|  
me = " "\*depth + “#{k} (#{subtree.length})”  
if subtree.empty?  
me  
else  
[me, subtree.as\_tree( depth+1 )]  
end  
}.flatten.join( “\n” )  
end  
end

hash\_of\_hashes = lambda { Hash.new {|h,k| h[k] = hash\_of\_hashes.call} }  
item\_tree = hash\_of\_hashes.call

items = [ “CarRedFast”, “CarGreenSlow”, “Car”,  
“CarRedFastAgileSadCheeseBurger”, “CarRedFastAgileHappyJoy”,  
“GreenApplePie”, “GreenApple” ]  
items.each do |item|  
current = item\_tree  
item.scan( /[A-Z][a-z]+/ ).each{ |piece|  
current = current[piece]  
}  
end

puts item\_tree.as\_tree  
#=\> Green (1)  
#=\> Apple (1)  
#=\> Pie (0)  
#=\> Car (2)  
#=\> Red (1)  
#=\> Fast (1)  
#=\> Agile (2)  
#=\> Sad (1)  
#=\> Cheese (1)  
#=\> Burger (0)  
#=\> Happy (1)  
#=\> Joy (0)  
#=\> Green (1)  
#=\> Slow (0)

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:48am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/3 "2006-11-07T10:48:02Z")

</div>

x1 wrote:

/ …

> Please… Any suggestions at all…

Sure, no problem. I could write an example of a hash-based tree data  
structure that would print itself out in a logical way, but I am having  
a  
problem with your data.

Could you provide a better data example, one that shows its hierarchical  
nature more clearly?

In the meantime:

* * *

#!/usr/bin/ruby -w

# Step 1: create some sample data

array = [  
[“animal”,“fish”,“shark”],  
[“animal”,“fish”,“trout”],  
[“animal”,“fish”,“big”,“whale shark”],  
[“animal”,“moose”],  
[“animal”,“bear”],  
[“animal”,“small”,“squirrel”],  
[“plant”,“cactus”],  
[“plant”,“corn”],  
[“plant”,“daisy”],  
[“plant”,“big”,“oak tree”],  
[“element”,“silicon”],  
[“element”, “dense”,“uranium”],  
[“element”,“light”,“helium”],  
[“state”,“Ohio”],  
[“state”,“tiny”,“Rhode Island”]  
]

# Step 2: assemble data into hash tree

tree = {}

array.each do |record|  
node = tree  
record.each do |field|  
node[field] = {} unless node[field]  
node = node[field]  
end  
end

# Step 3: define recursive display function

def showTree(tab,node)  
ts = “\t” \* tab  
node.keys.sort.each do |key|  
puts “#{ts}#{key}”  
showTree((tab+1),node[key])  
end  
end

# Step 4: display the tree

showTree(0,tree)

* * *

Output:

animal  
bear  
fish  
big  
whale shark  
shark  
trout  
moose  
small  
squirrel  
element  
dense  
uranium  
light  
helium  
silicon  
plant  
big  
oak tree  
cactus  
corn  
daisy  
state  
Ohio  
tiny  
Rhode Island

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:48am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/4 "2006-11-07T10:48:02Z")

</div>

Jesus! Give me an hour or so to make sense of this. I’m so glad you  
provided this!! A++++++++++++

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:48am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/5 "2006-11-07T10:48:05Z")

</div>

Ok –

Phrogz, I find your script very interesting and I’ll learn a lot by  
going through it over and over. Thank you!

Paul, Sorry for the crappy data (it just happened to be what I was  
working w/ at the time)

One of the key items both of you two used which I was not aware of  
(and am ignorant for this) is the ability to use:  
current = item\_tree #Phrogz  
node = tree # Paul

So what this is doing, is creating a new hash at the new depth,  
without having to statically reference it. Nice. Yes, I’m a newb to  
OO.

Thanks guys

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:50am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/6 "2006-11-07T10:50:10Z")

</div>

x1 wrote:

> Team:  
> I’m looking for a pragmatic way of creating a tree from a list of  
> items without knowing the depth of each.

Here’s a good algorithm for constructing a formal concept lattice.

> **[System Unavailable](https://www.lanl.gov/errors/system-notification.php)**
>
> ${\_EscapeTool.xml($description)}

It’s not particularly pragmatic, but it’s fast and ultimately  
equivalent to what you’re trying to do.

'cid 'ooh

---

<div class="post-metadata">

**Author:** ![d0t1q](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/d/9e8a1a/32.png) [@d0t1q](https://www.ruby-forum.com/u/d0t1q)\
**Post date:** [November 7, 2006, 10:48am UTC](https://www.ruby-forum.com/t/managing-hierarchical-tree-like-data/74554/7 "2006-11-07T10:48:09Z")

</div>

Paul L. wrote:

> array.each do |record|  
> node = tree  
> record.each do |field|  
> node[field] = {} unless node[field]  
> node = node[field]  
> end  
> end

I like Paul’s simple solution better than my  
tricky-but-almost-obfuscated autovivifying Hash. One note (that I don’t  
think is golfing): the innermost code in the above can be rubyified as:  
node[field] ||= {}  
node = node[field]  
or simplified further (golfed?) to:  
node = ( node[field] ||= {} )