Build a Tree Structure in Java Without Recursion

Background

Tree structures are common for hierarchical data such as organization trees, menus, directories, etc. Recursive traversal is intuitive but can cause stack overflow and performance issues on large data sets.

Learning from zTree

zTree, a jQuery tree plugin, provides a simple‑data mode that converts a flat list of nodes into a nested tree. The core code resides in jquery.ztree.core.js around line 895, where the setting setting.data.simpleData.enable triggers transformTozTreeFormat. The method builds a temporary map ( tmpMap) of id → node and then iterates the list twice: first to fill the map, second to attach each node to its parent’s children array, or to the root list if no parent exists.

Key steps of the JavaScript implementation

Read configuration keys for id, parentId, and children.

Return early if data is empty or id key missing.

Create tmpMap for O(1) lookup of nodes by id.

Iterate the node array, linking each node to its parent’s children array when the parent exists and is not the node itself.

Collect root nodes and return the resulting tree array.

Java implementation

Following the same logic, a TreeNode class with id, parentId, and children fields is defined. TreeUtils.transformToTreeFormat creates an idNodeMap, iterates the list to populate it, then builds the tree by linking each node to its parent or adding it to rootNodes. A test class TreeTest demonstrates the conversion and prints the resulting JSON.

import lombok.Data;

import java.util.ArrayList;
import java.util.List;

@Data
public class TreeNode {
    private String id;
    private String parentId;
    private List<TreeNode> children;
    // other fields …
    public TreeNode(String id, String parentId) {
        this.id = id;
        this.parentId = parentId;
        this.children = new ArrayList<>();
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TreeUtils {
    public static List<TreeNode> transformToTreeFormat(List<TreeNode> nodes) {
        if (nodes == null || nodes.isEmpty()) {
            return Collections.emptyList();
        }
        Map<String, TreeNode> idNodeMap = new HashMap<>();
        for (TreeNode node : nodes) {
            idNodeMap.put(node.getId(), node);
        }
        List<TreeNode> rootNodes = new ArrayList<>();
        for (TreeNode node : nodes) {
            TreeNode parentNode = idNodeMap.get(node.getParentId());
            if (parentNode != null && !node.getId().equals(node.getParentId())) {
                if (parentNode.getChildren() == null) {
                    parentNode.setChildren(new ArrayList<>());
                }
                parentNode.getChildren().add(node);
            } else {
                rootNodes.add(node);
            }
        }
        return rootNodes;
    }
}

import com.google.gson.Gson;
import java.util.ArrayList;
import java.util.List;

public class TreeTest {
    public static void main(String[] args) {
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(new TreeNode("1", null)); // root
        nodes.add(new TreeNode("2", "1"));
        nodes.add(new TreeNode("3", "1"));
        nodes.add(new TreeNode("4", "2"));
        nodes.add(new TreeNode("5", "2"));
        nodes.add(new TreeNode("6", "3"));
        nodes.add(new TreeNode("7", null)); // another root
        nodes.add(new TreeNode("8", "7"));
        nodes.add(new TreeNode("9", "8"));
        nodes.add(new TreeNode("10", "8"));
        List<TreeNode> tree = TreeUtils.transformToTreeFormat(nodes);
        System.out.println(new Gson().toJson(tree));
    }
}

The algorithm avoids recursion, uses two linear passes, and relies on a hash map for constant‑time parent lookup, which improves performance and eliminates stack‑overflow risk for deep trees.

Advantages and limitations

Better performance and stability on large data sets compared with recursive approaches.

Can handle deeper trees without stack overflow.

Requires unique node ids and a valid parentId; otherwise the tree may be built incorrectly.

If child nodes appear before their parents in the input list, the algorithm still works because the map is built first, but duplicate ids or missing parents break the result.