<commit_before>---
title: 'A Simple Tree Building Algorithm'
:date: 2017-03-05
tags: 
---

It is, unfortunately, not that often that I get the opportunity to devise an algorithm to solve a problem at work. Most work simply doesn't require that kind of thinking. But I thoroughly enjoy that kind of thinking, and thus thoroughly enjoyed the most recent opportunity I had to employ it. The problem was simple (though I have simplified and abstracted it for this post as well): we have a database table of `things`, and these `things` have a parent-child hierarchy, and we need to display a tree of these `things` in our UI. So, let's dig in.

First, let's examine the basic shape of the database table. Each `thing` has an _id_, _name_, and _parent\_id_, like so:

{:.tables}
| id | name | parent_id |
|----|------|-----------|
|  1 | A    | nil       |
|  2 | B    | 1         |
|  3 | C    | 1         |
|  4 | D    | 2         |
|  5 | E    | 4         |
|  6 | F    | 3         |
|  7 | G    | nil       |


Each row in the table gives us a "node" for our tree and tells us about that node's parent. This means that we cannot know by looking at a single row whether or not that "node" will have any children, but we can know if that "node" has a parent and what other "node" that parent is. If we want to think of this data in Ruby, this would be an array of hashes:

~~~ruby
[<commit_msg>Add tags to tree building article<commit_after>---
title: 'A Simple Tree Building Algorithm'
:date: 2017-03-05
tags: code, ruby
---

It is, unfortunately, not that often that I get the opportunity to devise an algorithm to solve a problem at work. Most work simply doesn't require that kind of thinking. But I thoroughly enjoy that kind of thinking, and thus thoroughly enjoyed the most recent opportunity I had to employ it. The problem was simple (though I have simplified and abstracted it for this post as well): we have a database table of `things`, and these `things` have a parent-child hierarchy, and we need to display a tree of these `things` in our UI. So, let's dig in.

First, let's examine the basic shape of the database table. Each `thing` has an _id_, _name_, and _parent\_id_, like so:

{:.tables}
| id | name | parent_id |
|----|------|-----------|
|  1 | A    | nil       |
|  2 | B    | 1         |
|  3 | C    | 1         |
|  4 | D    | 2         |
|  5 | E    | 4         |
|  6 | F    | 3         |
|  7 | G    | nil       |


Each row in the table gives us a "node" for our tree and tells us about that node's parent. This means that we cannot know by looking at a single row whether or not that "node" will have any children, but we can know if that "node" has a parent and what other "node" that parent is. If we want to think of this data in Ruby, this would be an array of hashes:

~~~ruby
[
{'fraction_non_alphanumeric': 0.09210526315789473, 'fraction_numerical': 0.01422475106685633, 'mean_word_length': 2.5834394904458597, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4152751', 'n_tokens_mistral': 840, 'n_tokens_neox': 787, 'n_words': 465}