title: Rendering a tree from a closure table SELECT statement?
body: <p><a href="https://stackoverflow.com/q/16065016/374470">[previous question]</a></p>
  
  <p>I'm trying to add reddit-like comments to an app, and I decided to go with the closure table pattern for database organization. My app database looks somewhat like this:</p>
  
  <h3>posts</h3>
  
  <pre><code>+----+-------+
  | id | title |
  +----+-------+
  |  1 | Hello |
  +----+-------+
  </code></pre>
  
  <h3>comments</h3>
  
  <pre><code>+----+-----------+---------+------+
  | id | parent_id | post_id | text |
  +----+-----------+---------+------+
  |  1 |      NULL |       1 | ...  |
  |  2 |         1 |       1 | ...  |
  |  3 |         2 |       1 | ...  |
  |  4 |         3 |       1 | ...  |
  |  5 |         3 |       1 | ...  |
  |  6 |         5 |       1 | ...  |
  |  7 |      NULL |       1 | ...  |
  |  8 |         7 |       1 | ...  |
  |  9 |         4 |       1 | ...  |
  +----+-----------+---------+------+
  </code></pre>
  
  <h3>comment_paths</h3>
  
  <pre><code>+-----------+----------+-------+
  | parent_id | child_id | depth |
  +-----------+----------+-------+
  |         1 |        1 |     0 |
  |         2 |        2 |     0 |
  |         1 |        2 |     1 |
  |         3 |        3 |     0 |
  |         2 |        3 |     1 |
  |         1 |        3 |     2 |
  |         4 |        4 |     0 |
  |         3 |        4 |     1 |
  |         2 |        4 |     2 |
  |         1 |        4 |     3 |
            [...snip...]
  </code></pre>
  
  <p>Right now, I'm running a this query:</p>
  
  <pre><code>SELECT c.*, p.*
  FROM comments AS c
  JOIN comment_paths AS p
      ON c.id = p.child_id
  WHERE p.parent_id IN
      (SELECT c2.id FROM comments AS c2 WHERE c2.parent_id IS NULL AND c2.post_id = 1)
  </code></pre>
  
  <p>to get a list of the comments based on their <code>post_id</code>. The returned data is:</p>
  
  <pre><code>+------+-------------+-----------+--------+-------------+------------+---------+
  | c.id | c.parent_id | c.post_id | c.text | p.parent_id | p.child_id | p.depth |
  +------+-------------+-----------+--------+-------------+------------+---------+
  |    1 |        NULL |         1 | ...    |           1 |          1 |       0 |
  |    2 |           1 |         1 | ...    |           1 |          2 |       1 |
  |    3 |           2 |         1 | ...    |           1 |          3 |       2 |
  |    4 |           3 |         1 | ...    |           1 |          4 |       3 |
  |    5 |           3 |         1 | ...    |           1 |          5 |       3 |
  |    6 |           5 |         1 | ...    |           1 |          6 |       4 |
  |    9 |           4 |         1 | ...    |           1 |          9 |       4 |
  |    7 |        NULL |         1 | ...    |           7 |          7 |       0 |
  |    8 |           7 |         1 | ...    |           7 |          8 |       1 |
  +------+-------------+-----------+--------+-------------+------------+---------+
  </code></pre>
  
  <p>This represents the tree:</p>
  
  <pre><code>[1]
   |[2]
   | |[3]
   |   |[4]
   |   | |[9]
   |  [5]
   |   |[6]
  [7]
   |[8]
  </code></pre>
  
  <p>However, I'm struggling to convert the returned data into a Python tree structure. Essentially, my goal is <a href="https://stackoverflow.com/questions/2794638/turn-database-result-into-array">this question</a> and <a href="https://stackoverflow.com/questions/12986914/how-can-i-display-tree-structure-in-html-from-closure-table">this question</a> in terms of final output (HTML) but I really don't want to resort to recursive SQL statements since I already have the information. I figure some sort of recursion is necessary, as I would like to end up with structure similar to this:</p>
  
  <pre><code>[
    {
      'id': 1,
      ...
      'children': [
                    {
                      'id': 2,
                      ...
                      'children': [ ... ]
                    }
                  ]
    },
    {
      'id': 7,
      ...
      'children': [
                  {
                    'id': 8,
                    ...
                  }
                ]
    }
  ]
  </code></pre>
  
  <p>Basically a nested list of dictionaries so I can loop over them using <a href="https://stackoverflow.com/a/6987333/374470">Jinja's recursive loop</a>. Does anyone have an idea?</p>
  
  <p>Thanks!</p>
  
  <hr>
  
  <h2>Edit 2013-04-17</h2>
  
  <p>Messing around, I have a "working" solution, although it does a lot of iterations so I don't want to mark it as the answer to this question. The solution I used is:</p>
  
  <pre><code>comment_set = ... # previous query to grab data set
  
  def create_tree(parent):
      parent['children'] = []
      for record in comment_set:
          if record['parent_id'] == parent['id']:
              parent['children'].append(create_tree(record))
      return parent
  
  comment_tree = []
  for record in comment_set:
      if record['parent_id'] is None: # if this is the start of a tree
          comment_tree.append(create_tree(record))
  </code></pre>
  
  <p>It's not ideal because it iterates over the <code>comment_set</code> every time <code>create_tree()</code> is called, which is every record in the set. However, it's the best I have right now. Anyone have any thoughts?</p>