How to build a tree from a flat structure?

Question

I have a bunch of objects in a flat structure. These objects have an ID and a ParentID property so they can be arranged in trees. They are in no particular order.

Each ParentID property does not necessarily matches with an ID in the structure. Therefore their could be several trees emerging from these objects.

How can I process these objects to create the resulting trees?

I need to create these trees to then insert Data into a database, in proper order.

There are no circular references. A Node is a RootNode when ParentID == null or when ParentID can't be found in the other objects.

• D'Arcy Rittich: What do you mean by "create"? Render in a UI? Store in a hierarchical fashion in XML or a database?
• user6212: How do you define a node with no parent (i.e. a root node). ParentID is null? ParentID = 0? I assume there are no circular references correct?
• ebram khalil: check out this article: scip.be/index.php?Page=ArticlesNET23&Lang=NL

Answer 1

Store IDs of the objects in a hash table mapping to the specific object. Enumerate through all the objects and find their parent if it exists and update its parent pointer accordingly.

In C#:

class MyObject
{ // The actual object
 public int ParentID { get; set; }
 public int ID { get; set; }
}
class Node
{
 public List<Node> Children = new List<Node>();
 public Node Parent { get; set; }
 public MyObject AssociatedObject { get; set; }
}
IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
 Dictionary<int, Node> lookup = new Dictionary<int, Node>();
 actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x }));
 foreach (var item in lookup.Values) {
 Node proposedParent;
 if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) {
 item.Parent = proposedParent;
 proposedParent.Children.Add(item);
 }
 }
 return lookup.Values.Where(x => x.Parent == null);
}

• Andrew Hanlon: This algo is (in informal notation) O(3N), where as an O(1N) solution is easily achievable by either instantiating partial Nodes for non 'traversed' parents OR by keeping a secondary look-up tables for children of non-instantiated parents. Likely does not matter for most real-world uses, but it could be significant on large data sets.
• Ced: @AndrewHanlon maybe you should post the sol for 0(1N)
• Andrew Hanlon: @Ced Martin Schmidt's answer below is very close to how I would implement it. As can be seen, it uses a single loop and the rest are hashtable operations.
• JakeWilson801: O(3N) is just O(N) ;)

Answer 2

Here is a simple JavaScript algorithm to parse a flat table into a parent/child tree structure that runs in N time:

var table = [
 {parent_id: 0, id: 1, children: []},
 {parent_id: 0, id: 2, children: []},
 {parent_id: 0, id: 3, children: []},
 {parent_id: 1, id: 4, children: []},
 {parent_id: 1, id: 5, children: []},
 {parent_id: 1, id: 6, children: []},
 {parent_id: 2, id: 7, children: []},
 {parent_id: 7, id: 8, children: []},
 {parent_id: 8, id: 9, children: []},
 {parent_id: 3, id: 10, children: []}
];
var root = {id:0, parent_id: null, children: []};
var node_list = { 0 : root};
for (var i = 0; i < table.length; i++) {
 node_list[table[i].id] = table[i];
 node_list[table[i].parent_id].children.push(node_list[table[i].id]);
}
console.log(root);

• hakan: realized that if id starts from something big like 1001 then we get index out of bound exception...
• aloisdg: Tip: use console.log(JSON.stringify(root, null, 2)); to pretty print the output.
• AaA: This will fail if nodes are not sorted by parent id

Answer 3

Based on the answer by Mehrdad Afshari and the comment of Andrew Hanlon for a speedup, here is my take.

Important difference to the original task: A root node has ID==parentID.

class MyObject
{ // The actual object
 public int ParentID { get; set; }
 public int ID { get; set; }
}
class Node
{
 public List<Node> Children = new List<Node>();
 public Node Parent { get; set; }
 public MyObject Source { get; set; }
}
List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects)
{
 var lookup = new Dictionary<int, Node>();
 var rootNodes = new List<Node>();
 foreach (var item in actualObjects)
 {
 // add us to lookup
 Node ourNode;
 if (lookup.TryGetValue(item.ID, out ourNode))
 { // was already found as a parent - register the actual object
 ourNode.Source = item;
 }
 else
 {
 ourNode = new Node() { Source = item };
 lookup.Add(item.ID, ourNode);
 }
 // hook into parent
 if (item.ParentID == item.ID)
 { // is a root node
 rootNodes.Add(ourNode);
 }
 else
 { // is a child row - so we have a parent
 Node parentNode;
 if (!lookup.TryGetValue(item.ParentID, out parentNode))
 { // unknown parent, construct preliminary parent
 parentNode = new Node();
 lookup.Add(item.ParentID, parentNode);
 }
 parentNode.Children.Add(ourNode);
 ourNode.Parent = parentNode;
 }
 }
 return rootNodes;
}

• Andrew Hanlon: Nice, this is basically the approach I was alluding to. I would however just use a pseudo root node (with ID = 0 and null Parent) and remove the self reference requirement.
• Philip Stanislaus: Since I could not find a npm module which implements a O(n) solution, I created the following one (unit tested, 100% code coverage, only 0.5 kb in size and includes typings. Maybe it helps someone: npmjs.com/package/performant-array-to-tree

Answer 4

Python solution

 def subtree(node, relationships):
 return {
 v: subtree(v, relationships) 
 for v in [x[0] for x in relationships if x[1] == node]
 }

For example:

 # (child, parent) pairs where -1 means no parent 
 flat_tree = [
 (1, -1),
 (4, 1),
 (10, 4),
 (11, 4),
 (16, 11),
 (17, 11),
 (24, 17),
 (25, 17),
 (5, 1),
 (8, 5),
 (9, 5),
 (7, 9),
 (12, 9),
 (22, 12),
 (23, 12),
 (2, 23),
 (26, 23),
 (27, 23),
 (20, 9),
 (21, 9)
 ]
 
 subtree(-1, flat_tree)

Produces:

 {
 "1": {
 "4": {
 "10": {}, 
 "11": {
 "16": {}, 
 "17": {
 "24": {}, 
 "25": {}
 }
 }
 }, 
 "5": {
 "8": {}, 
 "9": {
 "20": {}, 
 "12": {
 "22": {}, 
 "23": {
 "2": {}, 
 "27": {}, 
 "26": {}
 }
 }, 
 "21": {}, 
 "7": {}
 }
 }
 }
 }

• simple guy: Hi. How do I add another attribute in the output? ie. name, parent_id
• ccpizza: @simpleguy: the list comprehension can be unfolded in case you need more control, e.g.: def recurse(id, pages): for row in rows: if row['id'] == id: print(f'''{row['id']}:{row['parent_id']} {row['path']} {row['title']}''') recurse(row['id'], rows)

Answer 5

JS version that returns one root or an array of roots each of which will have a Children array property containing the related children. Does not depend on ordered input, decently compact, and does not use recursion. Enjoy!

 // creates a tree from a flat set of hierarchically related data
 var MiracleGrow = function(treeData, key, parentKey)
 {
 var keys = [];
 treeData.map(function(x){
 x.Children = [];
 keys.push(x[key]);
 });
 var roots = treeData.filter(function(x){return keys.indexOf(x[parentKey])==-1});
 var nodes = [];
 roots.map(function(x){nodes.push(x)});
 while(nodes.length > 0)
 {
 
 var node = nodes.pop();
 var children = treeData.filter(function(x){return x[parentKey] == node[key]});
 children.map(function(x){
 node.Children.push(x);
 nodes.push(x)
 });
 }
 if (roots.length==1) return roots[0];
 return roots;
 }
 
 
 // demo/test data
 var treeData = [
 
 {id:9, name:'Led Zep', parent:null},
 {id:10, name:'Jimmy', parent:9},
 {id:11, name:'Robert', parent:9},
 {id:12, name:'John', parent:9},
 
 {id:8, name:'Elec Gtr Strings', parent:5},
 {id:1, name:'Rush', parent:null},
 {id:2, name:'Alex', parent:1},
 {id:3, name:'Geddy', parent:1},
 {id:4, name:'Neil', parent:1},
 {id:5, name:'Gibson Les Paul', parent:2},
 {id:6, name:'Pearl Kit', parent:4},
 {id:7, name:'Rickenbacker', parent:3},
 
 {id:100, name:'Santa', parent:99},
 {id:101, name:'Elf', parent:100},
 
 ];
 var root = MiracleGrow(treeData, "id", "parent")
 console.log(root)

• Jordi Nebot: This question is 7 years old and already has a voted and accepted answer. If you think you have a better solution, it'd be great to add some explanation to your code.
• Cody C: This approach works well for this unordered type of data.

Answer 6

Found an awesome JavaScript version here: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

Let’s say you have an array like this:

const models = [
 {id: 1, title: 'hello', parent: 0},
 {id: 2, title: 'hello', parent: 0},
 {id: 3, title: 'hello', parent: 1},
 {id: 4, title: 'hello', parent: 3},
 {id: 5, title: 'hello', parent: 4},
 {id: 6, title: 'hello', parent: 4},
 {id: 7, title: 'hello', parent: 3},
 {id: 8, title: 'hello', parent: 2}
];

And you want to have the objects nested like this:

const nestedStructure = [
 {
 id: 1, title: 'hello', parent: 0, children: [
 {
 id: 3, title: 'hello', parent: 1, children: [
 {
 id: 4, title: 'hello', parent: 3, children: [
 {id: 5, title: 'hello', parent: 4},
 {id: 6, title: 'hello', parent: 4}
 ]
 },
 {id: 7, title: 'hello', parent: 3}
 ]
 }
 ]
 },
 {
 id: 2, title: 'hello', parent: 0, children: [
 {id: 8, title: 'hello', parent: 2}
 ]
 }
];

Here’s a recursive function that makes it happen.

function getNestedChildren(models, parentId) {
 const nestedTreeStructure = [];
 const length = models.length;
 for (let i = 0; i < length; i++) { // for-loop for perf reasons, huge difference in ie11
 const model = models[i];
 if (model.parent == parentId) {
 const children = getNestedChildren(models, model.id);
 if (children.length > 0) {
 model.children = children;
 }
 nestedTreeStructure.push(model);
 }
 }
 return nestedTreeStructure;
}

Usuage:

const models = [
 {id: 1, title: 'hello', parent: 0},
 {id: 2, title: 'hello', parent: 0},
 {id: 3, title: 'hello', parent: 1},
 {id: 4, title: 'hello', parent: 3},
 {id: 5, title: 'hello', parent: 4},
 {id: 6, title: 'hello', parent: 4},
 {id: 7, title: 'hello', parent: 3},
 {id: 8, title: 'hello', parent: 2}
];
const nestedStructure = getNestedChildren(models, 0);

• Ed Randall: For every parentId it's looping the whole model - is this not O(N^2) ?

Answer 7

For anyone interested in a C# version of Eugene's solution, note that node_list is accessed as a map, so use a Dictionary instead.

Keep in mind that this solution only works if table is sorted by parent_id.

var table = new[]
{
 new Node { parent_id = 0, id = 1 },
 new Node { parent_id = 0, id = 2 },
 new Node { parent_id = 0, id = 3 },
 new Node { parent_id = 1, id = 4 },
 new Node { parent_id = 1, id = 5 },
 new Node { parent_id = 1, id = 6 },
 new Node { parent_id = 2, id = 7 },
 new Node { parent_id = 7, id = 8 },
 new Node { parent_id = 8, id = 9 },
 new Node { parent_id = 3, id = 10 },
};
var root = new Node { id = 0 };
var node_list = new Dictionary<int, Node>{
 { 0, root }
};
foreach (var item in table)
{
 node_list.Add(item.id, item);
 node_list[item.parent_id].children.Add(node_list[item.id]);
}

Node is defined as follows.

class Node
{
 public int id { get; set; }
 public int parent_id { get; set; }
 public List<Node> children = new List<Node>();
}

• Disappointed: Looks it will fail for random nodes order. (for example,when root node will be in the end)

Answer 8

I converted Mehrdad Afshari's C# answer to Java:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class Tree {
 Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
 Map<Integer, Node> lookup = new HashMap<>();
 actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
 //foreach (var item in lookup.Values)
 lookup.values().forEach(item ->
 {
 Node proposedParent;
 if (lookup.containsKey(item.associatedObject.parentId)) {
 proposedParent = lookup.get(item.associatedObject.parentId);
 item.parent = proposedParent;
 proposedParent.children.add(item);
 }
 }
 );
 //return lookup.values.Where(x =>x.Parent ==null);
 return lookup.values().stream().filter(x -> x.parent == null).iterator();
 }
}
class MyObject { // The actual object
 public int parentId;
 public int id;
}
class Node {
 public List<Node> children = new ArrayList<Node>();
 public Node parent;
 public MyObject associatedObject;
 public Node(MyObject associatedObject) {
 this.associatedObject = associatedObject;
 }
}

Answer 9

I wrote a generic solution in C# loosely based on @Mehrdad Afshari answer:

void Example(List<MyObject> actualObjects)
{
 List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1);
}
public class TreeNode<T>
{
 public TreeNode(T value)
 {
 Value = value;
 Children = new List<TreeNode<T>>();
 }
 public T Value { get; private set; }
 public List<TreeNode<T>> Children { get; private set; }
}
public static class TreeExtensions
{
 public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey))
 {
 var roots = new List<TreeNode<TValue>>();
 var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(overrideValue)).ToArray();
 var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value));
 foreach (var currentNode in allNodes)
 {
 TKey parentKey = parentKeySelector(currentNode.Value);
 if (Equals(parentKey, defaultKey))
 {
 roots.Add(currentNode);
 }
 else
 {
 nodesByRowId[parentKey].Children.Add(currentNode);
 }
 }
 return roots;
 }
}

Answer 10

Most of the answers assume you are looking to do this outside of the database. If your trees are relatively static in nature and you just need to somehow map the trees into the database, you may want to consider using nested set representations on the database side. Check out books by Joe Celko (or here for an overview by Celko).

If tied to Oracle dbs anyway, check out their CONNECT BY for straight SQL approaches.

With either approach, you could completely skip mapping the trees before you load the data up in the database. Just thought I would offer this up as an alternative, it may be completely inappropriate for your specific needs. The whole "proper order" part of the original question somewhat implies you need the order to be "correct" in the db for some reason? This might push me towards handling the trees there as well.

Answer 11

Vague as the question seems to me, I would probably create a map from the ID to the actual object. In pseudo-java (I didn't check whether it works/compiles), it might be something like:

Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();
for (FlatObject object: flatStructure) {
 flatObjectMap.put(object.ID, object);
}

And to look up each parent:

private FlatObject getParent(FlatObject object) {
 getRealObject(object.ParentID);
}
private FlatObject getRealObject(ID objectID) {
 flatObjectMap.get(objectID);
}

By reusing getRealObject(ID) and doing a map from object to a collection of objects (or their IDs), you get a parent->children map too.

Answer 12

I can do this in 4 lines of code and O(n log n) time, assuming that Dictionary is something like a TreeMap.

dict := Dictionary new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | (dict at: each parent) addChild: each].
root := dict at: nil.

EDIT: Ok, and now I read that some parentIDs are fake, so forget the above, and do this:

dict := Dictionary new.
dict at: nil put: OrderedCollection new.
ary do: [:each | dict at: each id put: each].
ary do: [:each | 
 (dict at: each parent ifAbsent: [dict at: nil]) 
 add: each].
roots := dict at: nil.

Answer 13

It's not exactly the same as what the asker looked for, but I had difficulty wrapping my head around the ambiguously phrased answers provided here, and I still think this answer fits under the title.

My answer is for mapping a flat structure to a directly-on-object tree where all you have is a ParentID on each object. ParentID is null or 0 if it is a root. Opposite of the asker, I assume all valid ParentID's point to something else in the list:

var rootNodes = new List<DTIntranetMenuItem>();
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>();
//Convert the flat database items to the DTO's,
//that has a list of children instead of a ParentID.
foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List<tblIntranetMenuItem>
{
 //Automapper (nuget)
 DTIntranetMenuItem intranetMenuItem =
 Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem);
 intranetMenuItem.Children = new List<DTIntranetMenuItem>();
 dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem);
}
foreach (var efIntranetMenuItem in flatIntranetMenuItems)
{
 //Getting the equivalent object of the converted ones
 DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID];
 if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0)
 {
 rootNodes.Add(intranetMenuItem);
 }
 else
 {
 var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value];
 parent.Children.Add(intranetMenuItem);
 //intranetMenuItem.Parent = parent;
 }
}
return rootNodes;

Answer 14

here is a ruby implementation:

It will catalog by attribute name or the result of a method call.

CatalogGenerator = ->(depth) do
 if depth != 0
 ->(hash, key) do
 hash[key] = Hash.new(&CatalogGenerator[depth - 1])
 end
 else
 ->(hash, key) do
 hash[key] = []
 end
 end
end
def catalog(collection, root_name: :root, by:)
 method_names = [*by]
 log = Hash.new(&CatalogGenerator[method_names.length])
 tree = collection.each_with_object(log) do |item, catalog|
 path = method_names.map { |method_name| item.public_send(method_name)}.unshift(root_name.to_sym)
 catalog.dig(*path) << item
 end
 tree.with_indifferent_access
end
 students = [#<Student:0x007f891d0b4818 id: 33999, status: "on_hold", tenant_id: 95>,
 #<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b42c8 id: 37220, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b4020 id: 3444, status: "ready_for_match", tenant_id: 15>,
 #<Student:0x007f8931d5ab58 id: 25166, status: "in_partnership", tenant_id: 10>]
catalog students, by: [:tenant_id, :status]
# this would out put the following
{"root"=>
 {95=>
 {"on_hold"=>
 [#<Student:0x007f891d0b4818
 id: 33999,
 status: "on_hold",
 tenant_id: 95>]},
 6=>
 {"on_hold"=>
 [#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b42c8
 id: 37220,
 status: "on_hold",
 tenant_id: 6>]},
 15=>
 {"ready_for_match"=>
 [#<Student:0x007f891d0b4020
 id: 3444,
 status: "ready_for_match",
 tenant_id: 15>]},
 10=>
 {"in_partnership"=>
 [#<Student:0x007f8931d5ab58
 id: 25166,
 status: "in_partnership",
 tenant_id: 10>]}}}

Answer 15

The accepted answer looks way too complex to me so I am adding a Ruby and NodeJS versions of it

Suppose that flat nodes list have the following structure:

nodes = [
 { id: 7, parent_id: 1 },
 ...
] # ruby
nodes = [
 { id: 7, parentId: 1 },
 ...
] # nodeJS

The functions which will turn the flat list structure above into a tree look the following way

for Ruby:

def to_tree(nodes)
 nodes.each do |node|
 parent = nodes.find { |another| another[:id] == node[:parent_id] }
 next unless parent
 node[:parent] = parent
 parent[:children] ||= []
 parent[:children] << node
 end
 nodes.select { |node| node[:parent].nil? }
end

for NodeJS:

const toTree = (nodes) => {
 nodes.forEach((node) => {
 const parent = nodes.find((another) => another.id == node.parentId)
 if(parent == null) return;
 node.parent = parent;
 parent.children = parent.children || [];
 parent.children = parent.children.concat(node);
 });
 return nodes.filter((node) => node.parent == null)
};

• Cabrera: I believe the check for null needs to be for undefined
• Hirurg103: @Ullauri null == undefined => true in NodeJS

Answer 16

one elegant way to do this is to represent items in the list as string holding a dot separated list of parents, and finally a value:

server.port=90
server.hostname=localhost
client.serverport=90
client.database.port=1234
client.database.host=localhost

When assembling a tree, you would end up with something like:

server:
 port: 90
 hostname: localhost
client:
 serverport=1234
 database:
 port: 1234
 host: localhost

I have a configuration library that implements this override configuration (tree) from command line arguments (list). The algorithm to add a single item to the list to a tree is here.

Answer 17

Golang solution utilizing pointer. Since each iteration will basically point to same object, resulting in N space & time complexity

https://go.dev/play/p/lrPBTawy7Su

func TestCommentTree(t *testing.T) {
 var listRaw = `[{"id":5,"parentPostID":0,"parentID":null,"authorID":1,"content":"asadas","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":9,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":10,"parentPostID":0,"parentID":9,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":11,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":12,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":13,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":14,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":15,"parentPostID":0,"parentID":12,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":16,"parentPostID":0,"parentID":11,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":17,"parentPostID":0,"parentID":16,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":18,"parentPostID":0,"parentID":17,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"},{"id":19,"parentPostID":0,"parentID":18,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001年01月01日T00:00:00Z","updatedAt":"0001年01月01日T00:00:00Z"}]`
 
 type Comment struct {
 ID uint64 `db:"id" json:"id"`
 ParentPostID uint64 `db:"parent_post_id" json:"parentPostID"`
 ParentID *int `db:"parent_id" json:"parentID"` // allow nullable on lvl 0 comment
 AuthorID uint64 `db:"author_id" json:"authorID"`
 Content string `db:"content" json:"content"`
 Replies []*Comment `json:"replies"`
 CreatedAt time.Time `db:"created_at" json:"createdAt"`
 UpdatedAt time.Time `db:"updated_at" json:"updatedAt"`
 }
 var c []*Comment
 err := json.Unmarshal([]byte(listRaw), &c)
 if err != nil {
 panic(err)
 }
 node := make(map[uint64]*Comment)
 for _, v := range c {
 node[v.ID] = v
 }
 for _, comm := range node {
 if comm.ParentID == nil {
 continue
 }
 parent := node[uint64(*comm.ParentID)]
 if parent == nil {
 panic(fmt.Sprintf("parent nil %d", *comm.ParentID))
 }
 if parent.Replies == nil {
 parent.Replies = make([]*Comment, 0)
 parent.Replies = append(parent.Replies, comm)
 } else {
 parent.Replies = append(parent.Replies, comm)
 }
 }
 res := make([]*Comment, 0)
 for _, comm := range node {
 if comm.ParentID != nil {
 continue
 }
 res = append(res, comm)
 }
 s, _ := json.MarshalIndent(res, "", "\t")
 fmt.Println(string(s))
}

Answer 18

Are you stuck using only those attributes? If not, it might be nice to create an array of child nodes, where you can cycle through all these objects once to build such attributes. From there, select the node with children but no parents and iteratively build your tree from the top down.

Answer 19

java version

// node
@Data
public class Node {
 private Long id;
 private Long parentId;
 private String name;
 private List<Node> children = new ArrayList<>();
}
// flat list to tree
List<Node> nodes = new ArrayList();// load nodes from db or network
Map<Long, Node> nodeMap = new HashMap();
nodes.forEach(node -> {
 if (!nodeMap.containsKey(node.getId)) nodeMap.put(node.getId, node);
 if (nodeMap.containsKey(node.getParentId)) {
 Node parent = nodeMap.get(node.getParentId);
 node.setParentId(parent.getId());
 parent.getChildren().add(node);
 }
});
// tree node
List<Node> treeNode = nodeMap .values().stream().filter(n -> n.getParentId() == null).collect(Collectors.toList());

Answer 20

Based on Euguene's answer, here is a functional approach. If the items are not pre-sorted, the nodeList will not have the parent ready to add children.

const sortByParentId = (
 { parentId: a1, id: a2 },
 { parentId: b1, id: b2 }
) => a1 - b1 || a2 - b2
const buildTree = (items) => {
 const
 root = { id: 0, parentId: null, children: [] },
 nodeList = { 0 : root };
 items
 .sort(sortByParentId)
 .forEach(({ id, parentId }) => {
 nodeList[id] = { id, parentId, children: [] };
 nodeList[parentId].children.push(nodeList[id]);
 });
 return root;
};
// Reversed (does not work without proper sorting)
const items = [
 { id: 10, parentId: 3 },
 { id: 9, parentId: 8 },
 { id: 8, parentId: 7 },
 { id: 7, parentId: 2 },
 { id: 6, parentId: 1 },
 { id: 5, parentId: 1 },
 { id: 4, parentId: 1 },
 { id: 3, parentId: 0 },
 { id: 2, parentId: 0 },
 { id: 1, parentId: 0 },
]; 
const tree = buildTree(items);
console.log(tree);

.as-console-wrapper { top: 0; max-height: 100% !important; }

<!--
// Best-case order
const items = [
 { id: 1, parentId: 0 },
 { id: 2, parentId: 0 },
 { id: 3, parentId: 0 },
 { id: 4, parentId: 1 },
 { id: 5, parentId: 1 },
 { id: 6, parentId: 1 },
 { id: 7, parentId: 2 },
 { id: 8, parentId: 7 },
 { id: 9, parentId: 8 },
 { id: 10, parentId: 3 }
]; 
-->

Here is an example without pre-sorting (with OOP):

class Node {
 constructor({ id, parentId }) {
 this.id = id;
 this.parentId = parentId;
 this.children = [];
 }
};
const buildTree = (items) => {
 const
 root = new Node({ id: 0, parentId: null }),
 nodeList = { 0 : root };
 items.forEach(({ id, parentId }) => {
 if (!nodeList[id]) {
 nodeList[id] = new Node({ id, parentId });
 } else {
 nodeList[id].parentId = parentId;
 }
 if (!nodeList[parentId]) {
 nodeList[parentId] = new Node({ id: parentId });
 }
 nodeList[parentId].children.push(nodeList[id]);
 });
 return root;
};
const items = [
 { id: 10, parentId: 3 },
 { id: 8, parentId: 7 },
 { id: 6, parentId: 1 },
 { id: 4, parentId: 1 },
 { id: 2, parentId: 0 },
 { id: 9, parentId: 8 },
 { id: 7, parentId: 2 },
 { id: 5, parentId: 1 },
 { id: 3, parentId: 0 },
 { id: 1, parentId: 0 },
]; 
const tree = buildTree(items);
console.log(tree);

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 21

This is a complete Java 8+ solution with a modification to Vimal Bhatt's version that accepts more than one root:

package tree;
import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Stream;
public class Tree {
 
 private <T> void swap(T[] input, int a, int b) {
 T tmp = input[a];
 input[a] = input[b];
 input[b] = tmp;
 }
 
 public static void main(String[] args) {
 Random r = new Random(8);
 MyObject[] myObjects = new MyObject[]{
 new MyObject(6, 3),
 new MyObject(7, 5),
 new MyObject(8, 0),
 new MyObject(1, 0),
 new MyObject(15, 12),
 new MyObject(12, 0),
 new MyObject(3, 5),
 new MyObject(4, 3),
 new MyObject(5, 2),
 new MyObject(2, 1),
 new MyObject(21, 8),
 new MyObject(9, 1)
 };
 
 Tree t = new Tree();
 // cinco trocas arbitrarias de posição
 for (int i = 0; i < 5; i++) {
 int a = r.nextInt(7) + 1;
 int b = r.nextInt(7) + 1;
 t.swap(myObjects, a, b);
 }
 System.out.println("The list have " + myObjects.length + " objects");
 for (MyObject o: myObjects) {
 System.out.print(" " + o);
 }
 Iterator<Node> iterator = t.buildTreeAndGetRoots(Arrays.asList(myObjects));
 int counter = 0;
 System.out.println("");
 while (iterator.hasNext()) {
 Node obj = iterator.next();
 System.out.println(++counter + "\t" + obj.associatedObject.id + "\t-> " + obj.associatedObject.parentId);
 }
 }
 Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
 Node root = null;
 Map<Integer, Node> lookup = new HashMap<>();
 actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
 Stream<Node> roots = actualObjects.stream()
 .filter(x -> x.parentId == 0)
 .map(x -> new Node(x));
 Consumer<Node> nodeConsumer = item -> {
 Node proposedParent;
 if (lookup.containsKey(item.associatedObject.parentId)) {
 proposedParent = lookup.get(item.associatedObject.parentId);
 item.parent = proposedParent;
 proposedParent.children.add(item);
 }
 };
 lookup.values().forEach(nodeConsumer);
 Stream<Node> s2 = lookup.values().stream().filter(e -> e.associatedObject.parentId != 0);
 return Stream.concat(roots, s2).iterator();
 }
}
class MyObject { // The actual object
 public int parentId;
 public int id;
 MyObject(int id, int parent) {
 this.parentId = parent;
 this.id = id;
 }
 @Override
 public String toString() {
 return "{ " +
 "parent: " + parentId +
 ", id: " + id +
 " }" ;
 }
}
class Node {
 public List<Node> children = new ArrayList<Node>();
 public Node parent;
 public MyObject associatedObject;
 public Node(MyObject associatedObject) {
 this.associatedObject = associatedObject;
 }
}