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

Model the comments as a tree. The parent pointers form an adjacency list, so we build the tree at write time and keep the read path cheap. One pass over the comments creates a Map<Long, List<CommentNode>> grouping children by parentId. Comments with parentId == 0 are the roots. For each root we recursively attach children, sorting siblings at every level by the requested SortType (rating or date) using a pluggable comparator. Reads are a DFS flatten over the cached tree, parents followed immediately by their sorted children.

Pay the cost at ingestion, keep reads cheap.

Implementation

CommentNode, the 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, a 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 exposes a single GET endpoint with a 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