tree.md

Problem Description

Reddit.com has a tree presentation for the posts. For example:

https://www.reddit.com/r/programming/comments/2szuc2/creating_a_doomstyle_3d_engine_in_c_code_walk_and/

The topic has more than 200 posts, and it shows the "top 200 comments". The tree layout shows the comments about the topic, and context association.

Assume all posts are stored in the relational database as a set of unsorted records. When load all of comments for a specific topic, a program has to build the pretty tree layout. This program uses the JSON array to store the abstracted data records as:

<id, parent_id>
    id: unique post id
    parent_id: point to the parent post id

For a given topic, there is a root record, id is 1, and parent_id is 0. Other post ids are bigger than the root record.

Input Data Examples

Example 1

{topic1_posts: [
    {id: 1, parent_id: 0},
    {id: 2, parent_id: 1},
    {id: 3, parent_id: 1}
]}
Output:
    id-1:
    |
    +-->id-2
    |
    +-->id-3

Example 2

{topic2_posts: [
    {id: 6, parent_id: 2},
    {id: 4, parent_id: 3},
    {id: 3, parent_id: 1},
    {id: 5, parent_id: 2},
    {id: 2, parent_id: 1},
    {id: 1, parent_id: 0},
    {id: 7, parent_id: 3}
]}

Example 3

// accept with non-continuous (gap - two trees, two roots)

{topic3_posts: [
    {id: 3, parent_id: 1},
    {id: 5, parent_id: 3},
    {id: 2, parent_id: 1},
    {id: 1, parent_id: 0}
]}

Example 4

// not accept - this is a loop, not a tree/DAG

{topic4_posts: [
    {id: 6, parent_id: 3},
    {id: 4, parent_id: 3},
    {id: 3, parent_id: 7},
    {id: 5, parent_id: 2},
    {id: 2, parent_id: 1},
    {id: 1, parent_id: 0},
    {id: 7, parent_id: 4}
]}