[Java] 특정 ID를 가진 노드의 하위 계층(Leaf)을 찾는 방법

이 글은 트리 구조 데이터를 다루는 과정에서 특정 ID를 가진 노드를 찾고, 그 노드의 하위 계층 중 leaf 노드를 효율적으로 수집하는 방법에 대해 정리한 내용입니다. 실제 개발 과정에서 이러한 구조를 처리해야 할 필요가 생겼고, 해당 문제를 해결하기 위해 질의 및 코드 실험을 진행한 뒤 그 결과를 정리한 것입니다. 본 글에서는 가능한 한 일반화된 형태의 코드와 함께 그 과정을 설명드리고자 합니다.

문제 정의

본 글에서 다루는 트리 구조는 다음과 같은 특징을 가지고 있다고 가정합니다.

• 루트 노드가 여러 개 존재할 수 있다: List<Node> roots
• 각 노드는 자식 노드를 나타내는 배열을 가진다: Node[] children
• 각 노드는 고유 ID를 가진다: String id
• 해결해야 하는 핵심 문제는 다음과 같다.
  • 전체 트리에서 특정 ID를 가진 노드를 우선적으로 탐색
  • 해당 노드를 기준으로 leaf 노드를 모두 수집

특정 ID가 트리의 가장 상위 레벨에 존재할 수도 있고, 중간 혹은 더 깊은 레벨에 존재할 수도 있기 때문에 전체 탐색이 필요합니다. 이러한 이유로 DFS(Depth-First Search)를 기반으로 한 탐색이 적합합니다.

코드/방법

전체 구현은 다음과 같이 세 단계로 구성됩니다.

1. findNodeById
   여러 개의 루트 노드에서 특정 ID를 가진 노드를 검색합니다.
2. collectLeafNodes
   찾은 노드를 기준으로, 자식이 없는 leaf 노드를 모두 수집합니다.
3. findLeafNodesById
   위 두 기능을 결합하여 특정 ID를 입력하면 해당 노드 하위의 leaf 노드를 반환하는 형태로 제공합니다.

Node 클래스 예시

public class Node {
    private String id;
    private Node[] children;

    public Node(String id, Node[] children) {
        this.id = id;
        this.children = children;
    }

    public String getId() {
        return id;
    }

    public Node[] getChildren() {
        return children;
    }
}

전체 구현 코드

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

public class TreeUtils {

    // 여러 루트에서 특정 ID를 가진 노드 찾기
    public static Node findNodeById(List<Node> roots, String targetId) {
        if (roots == null || roots.isEmpty() || targetId == null) {
            return null;
        }

        for (Node root : roots) {
            Node found = findNodeById(root, targetId);
            if (found != null) {
                return found;
            }
        }
        return null;
    }

    // 단일 노드에서 DFS로 검색
    private static Node findNodeById(Node node, String targetId) {
        if (node == null) return null;

        if (targetId.equals(node.getId())) {
            return node;
        }

        Node[] children = node.getChildren();
        if (children == null || children.length == 0) {
            return null;
        }

        for (Node child : children) {
            Node found = findNodeById(child, targetId);
            if (found != null) return found;
        }
        return null;
    }

    // leaf 노드를 수집
    private static void collectLeafNodes(Node node, List<Node> result) {
        if (node == null) return;

        Node[] children = node.getChildren();

        if (children == null || children.length == 0) {
            result.add(node);
            return;
        }

        for (Node child : children) {
            collectLeafNodes(child, result);
        }
    }

    // ID 기준으로 leaf 노드를 모두 반환
    public static List<Node> findLeafNodesById(List<Node> roots, String targetId) {
        Node start = findNodeById(roots, targetId);

        if (start == null) {
            return Collections.emptyList();
        }

        List<Node> result = new ArrayList<>();
        collectLeafNodes(start, result);
        return result;
    }
}

결과/출력

아래와 같이 해당 기능을 사용할 수 있습니다.

List<Node> roots = Arrays.asList(root1, root2, root3);

List<Node> leaves = TreeUtils.findLeafNodesById(roots, "A");

for (Node leaf : leaves) {
    System.out.println(leaf.getId());
}

• ID A가 leaf 노드라면 A만 반환됩니다.
• A가 중간 계층일 경우, A 하위에 존재하는 모든 leaf 노드가 반환됩니다.
• A가 트리 내 어디에 있든 전체 탐색을 통해 정상적으로 검색할 수 있습니다.

응용/팁

• 자식 구조가 배열이 아니라 List<Node> 형태라면 isEmpty() 등을 활용하여 동일한 방식으로 처리할 수 있습니다.
• leaf가 아닌 가장 깊은 깊이(depth)의 단일 노드를 찾고자 할 경우 depth 정보를 추가하면 쉽게 확장할 수 있습니다.
• 특정 ID까지의 경로(path)를 함께 반환하는 기능 또한 DFS 기반으로 손쉽게 구현할 수 있습니다.

결론

트리 구조 탐색은 구조가 복잡해질수록 유지보수가 어려울 수 있지만, 기능을 분리하고 일반화하면 재사용성이 크게 향상됩니다. 이번 작업을 통해 특정 ID를 가진 노드를 효율적으로 검색하고, 하위 계층의 leaf 노드를 손쉽게 수집할 수 있도록 구조화된 방식을 마련할 수 있었습니다. 이러한 접근은 위치 구조, 메뉴 구조, 카테고리 구조 등 다양한 트리 기반 데이터에 적용할 수 있다는 점에서 실용적입니다.