Mastering Generic Tree Construction in Java: A Robust TreeBuilder Utility

Design Philosophy and Core Features

TreeBuilder is a generic utility for building tree structures from a flat list of nodes. It supports any node type via generic parameters T (data) and K (ID type).

Multi‑type support : works with arbitrary data and ID types.

Automatic construction : root nodes are identified automatically and parent‑child relationships are wired without manual code.

Safety mechanisms : detects cyclic dependencies and duplicate IDs.

Extensible design : custom comparator and child‑setter interface allow custom sorting and child assignment.

Efficient querying : can build sub‑trees for search results.

Implementation Overview

1. Data Structure Preparation

Map<K, T> nodeMap = createNodeMap(items);
Map<K, List<T>> parentChildrenMap = items.stream()
    .collect(Collectors.groupingBy(parentIdGetter,
        LinkedHashMap::new,
        Collectors.toList()));

nodeMap provides O(1) lookup and duplicate detection; parentChildrenMap preserves insertion order for child lists.

2. Cyclic Dependency Detection

The algorithm traces each node’s ancestor chain using a LinkedHashSet to achieve O(n) time. It throws CyclicDependencyException when a direct self‑reference or an indirect cycle (e.g., A→B→C→A) is found.

Set<K> path = new LinkedHashSet<>();
while (tracingId != null) {
    if (!path.add(tracingId)) {
        throw new CyclicDependencyException(buildCyclePath(path, tracingId));
    }
    if (verifiedNodes.contains(tracingId)) break;
    K parentId = idToParentMap.get(tracingId);
    if (parentId == null) break;
    if (parentId.equals(tracingId)) {
        throw new CyclicDependencyException("Direct cyclic dependency: " + tracingId);
    }
    tracingId = parentId;
}
verifiedNodes.addAll(path);

3. Tree Construction

Two‑phase process: first populate each node’s child list (sorted by the provided comparator), then filter root nodes (parent ID is null or missing).

nodeMap.forEach((nodeId, node) -> {
    List<T> children = parentChildrenMap.getOrDefault(nodeId, Collections.emptyList())
        .stream()
        .sorted(comparator)
        .collect(Collectors.toList());
    childSetter.setChildren(node, Collections.unmodifiableList(children));
});
return items.stream()
    .filter(item -> isRootNode(item, nodeMap))
    .sorted(comparator)
    .collect(Collectors.toList());

4. Search Sub‑Tree Generation

For search scenarios the utility collects all ancestor IDs of matched nodes and builds a minimal tree containing those paths.

Set<K> relatedIds = findRelatedIds(allItems, matchIds);
List<T> relatedItems = allItems.stream()
    .filter(item -> relatedIds.contains(idGetter.apply(item)))
    .collect(Collectors.toList());
return buildTree(relatedItems);

Key Code Details

Node Sorting

Natural order via createWithNaturalOrder.

Custom comparator for business‑specific ordering.

Exception Handling

public static class CyclicDependencyException extends RuntimeException {
    public CyclicDependencyException(String message) {
        super(message);
    }
}

The exception message includes the detected cycle, e.g., “Detected cyclic dependency chain: 1001 → 1002 → 1003 → 1001”.

Functional Interface

@FunctionalInterface
public interface ChildSetter<T> {
    void setChildren(T parent, List<T> children);
}

Clients supply a lambda such as (parent, children) -> parent.setChildren(children) to define how children are attached.

Usage Examples

Basic Usage

List<Menu> menus = getFromDB();
TreeBuilder<Menu, Integer> builder = TreeBuilder.create(
    Menu::getId,
    Menu::getParentId,
    (parent, children) -> parent.setChildren(children),
    Comparator.comparing(Menu::getSortOrder)
);
List<Menu> tree = builder.buildTree(menus);

Search Scenario

Set<Integer> matchIds = searchService.findIds("keyword");
List<Menu> resultTree = builder.buildSearchTree(allMenus, matchIds);

Precautions

ID Guidelines

IDs must correctly implement hashCode() and equals().

Prefer wrapper types (e.g., Long) to avoid primitive‑type mismatches.

Object State

Source objects should allow child collection assignment.

Using immutable collections helps prevent accidental modifications.

Special Cases

Empty input returns Collections.emptyList().

Orphan nodes become root nodes when their parent is missing.

Performance Considerations

For data sets larger than ten thousand items, consider batch processing.

Cache the nodeMap if the tree is built repeatedly.