Hierarchical Tree Flattening

REST API that returns comments sorted in parent-child order -- the tree-flattening problem you hit anytime you need to display threaded discussions.

Problem

Given a flat list of comments where each record has a parentId pointer, return them sorted so every child appears directly beneath its parent. Support sorting by rating or timestamp.

Approach

1. Model as a tree. The parent pointers form an adjacency list — build a tree at write time so the read path stays fast.
2. Map parent IDs to children. One pass through the comment list creates a Map<Long, List<CommentNode>> grouping children by parentId.
3. Identify roots. Comments with parentId == 0 are root nodes.
4. Recurse and sort. For each root, recursively attach children. At every level, sort siblings by the requested SortType (rating or date) using a pluggable comparator.
5. Flatten on read. A DFS traversal of the tree produces the final ordered list — parents followed immediately by their sorted children.

The tree is built once on the write path and reused across queries -- pay the cost at ingestion, keep reads cheap.

Implementation

CommentNode — tree node holding one comment and its sorted children:

public class CommentNode {

    private Comment comment;
    private Map<SortType, List<CommentNode>> children = new HashMap<>();

    public CommentNode(Comment comment) {
        this.comment = comment;
    }

    public void addChildren(SortType sortType, List<CommentNode> childNodes) {
        List<CommentNode> existing = children.computeIfAbsent(sortType, k -> new ArrayList<>());
        childNodes.sort(SortComparator.getComparator(sortType));
        existing.addAll(childNodes);
    }

    public List<Comment> getParentChilds(SortType sortType) {
        List<Comment> all = new ArrayList<>();
        flatten(sortType, all, this);
        return all;
    }

    private void flatten(SortType sortType, List<Comment> results, CommentNode node) {
        results.add(node.comment);
        for (CommentNode child : node.getChildren(sortType)) {
            flatten(sortType, results, child);
        }
    }

    public List<CommentNode> getChildren(SortType sortType) {
        return children.computeIfAbsent(sortType, k -> new ArrayList<>());
    }

    public boolean hasChildren(SortType sortType) {
        return children.containsKey(sortType) && !children.get(sortType).isEmpty();
    }

    public Comment getComment() { return comment; }
}

CommentTree — singleton that builds and caches the full tree:

public class CommentTree {

    private static final CommentTree instance = new CommentTree();
    private Map<SortType, List<CommentNode>> rootLevelComments = new HashMap<>();

    private CommentTree() {}
    public static CommentTree getInstance() { return instance; }

    public void buildSortTree(List<Comment> comments, SortType sortType) {
        // Group children by parentId
        Map<Long, List<CommentNode>> parentChildMap = new HashMap<>();
        for (Comment c : comments) {
            parentChildMap.computeIfAbsent(c.getParentId(), k -> new ArrayList<>())
                          .add(new CommentNode(c));
        }

        // Root nodes have parentId == 0
        List<CommentNode> roots = parentChildMap.getOrDefault(0L, new ArrayList<>());
        addRootLevelNodes(sortType, roots);

        for (CommentNode root : getRootLevelComments(sortType)) {
            buildRecursive(sortType, root, parentChildMap);
        }
    }

    private void buildRecursive(SortType sortType, CommentNode node,
                                Map<Long, List<CommentNode>> parentChildMap) {
        List<CommentNode> kids = parentChildMap.get(node.getComment().getCommentId());
        if (kids != null) node.addChildren(sortType, kids);
        for (CommentNode child : node.getChildren(sortType)) {
            buildRecursive(sortType, child, parentChildMap);
        }
    }

    public void addRootLevelNodes(SortType sortType, List<CommentNode> nodes) {
        List<CommentNode> existing = rootLevelComments.computeIfAbsent(sortType, k -> new ArrayList<>());
        nodes.sort(SortComparator.getComparator(sortType));
        existing.addAll(nodes);
    }

    public List<CommentNode> getRootLevelComments(SortType sortType) {
        return rootLevelComments.computeIfAbsent(sortType, k -> new ArrayList<>());
    }
}

SortComparator — pluggable comparators for rating and date:

public class SortComparator {

    public static Comparator<CommentNode> getComparator(SortType sortType) {
        switch (sortType) {
            case RATING: return (a, b) -> b.getComment().getRating().compareTo(a.getComment().getRating());
            case DATE:   return (a, b) -> b.getComment().getTimeStamp().compareTo(a.getComment().getTimeStamp());
            default:     return null;
        }
    }
}

CommentServiceImpl — lazy-builds the tree on first request:

@Service
public class CommentServiceImpl implements CommentService {

    @Autowired
    private CommentRepository commentRepository;

    @Override
    public List<Comment> getSortedComments(SortType sortType) {
        List<CommentNode> roots = CommentTree.getInstance().getRootLevelComments(sortType);

        if (roots.isEmpty()) {
            List<Comment> all = new ArrayList<>();
            commentRepository.findAll().forEach(all::add);
            CommentTree.getInstance().buildSortTree(all, sortType);
        }

        List<Comment> sorted = new ArrayList<>();
        for (CommentNode root : roots) {
            sorted.addAll(root.getParentChilds(sortType));
        }
        return sorted;
    }
}

CommentController — single GET endpoint with sort parameter:

@RestController
@RequestMapping("/api/comments")
public class CommentController {

    @Autowired
    private CommentService commentService;

    @GetMapping
    public List<Comment> getSortedComments(@RequestParam("sort") String sort) {
        if (sort == null || sort.isEmpty())
            throw new IllegalArgumentException("'sort' parameter required.");
        if (!sort.equalsIgnoreCase("RATING") && !sort.equalsIgnoreCase("DATE"))
            throw new IllegalArgumentException("Invalid sort — use RATING or DATE.");

        return commentService.getSortedComments(SortType.valueOf(sort.toUpperCase()));
    }
}

Complexity

• Time: O(n log n) for the initial tree build (sorting at each level), O(n) for subsequent reads via DFS flattening.
• Space: O(n) for the tree structure and the parent-child map.

Takeaway

Tree-building from flat parent pointers is a recurring pattern. Building the tree once on the write path and flattening on read keeps the API responsive under load.

---

Back to Microservices & APIs