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.

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);
}

Here is java solution of the answer by Mehrdad Afshari.

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;
    }
}

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.

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.

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.

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>]}}}

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)

};

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.

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.

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());

See below a complete Java 8+ solution with simple test program.

this is a solution with a modification to the @"Vimal Bhatt" 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;
    }
}

This solution is the same as the selected answer, but in JavaScript:

/**
 * @param {{id: any, parentId: any}[]} nodes
 */
function arrayToTree(nodes) {
  const map = new Map(nodes.map((x) => [x.id, { key: x.id, children: [] }]));
  for (const n of nodes) {
    if (n.parentId) {
      map.get(n.parentId)?.children?.push(map.get(n.id));
    }
  }
  return nodes.filter((x) => x.parentId === null).map((x) => map.get(x.id));
}

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-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":9,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":10,"parentPostID":0,"parentID":9,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":11,"parentPostID":0,"parentID":5,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":12,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":13,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":14,"parentPostID":0,"parentID":10,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":15,"parentPostID":0,"parentID":12,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":16,"parentPostID":0,"parentID":11,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":17,"parentPostID":0,"parentID":16,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":18,"parentPostID":0,"parentID":17,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00:00:00Z"},{"id":19,"parentPostID":0,"parentID":18,"authorID":1,"content":"yeet comment","replies":null,"createdAt":"0001-01-01T00:00:00Z","updatedAt":"0001-01-01T00: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))
}

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; }