JavaScript로 평면 배열을 트리 구조 배열로 변환하는 방법

JavaScript로 복잡한 JSON 파일을 다루다 보면, 데이터를 계층 구조로 만들어 트리(tree) 형태로 구성해야 하는 경우가 자주 있습니다. 예를 들어 카테고리 메뉴, 조직도, 폴더 구조 등을 렌더링할 때 평면(flat) 배열을 트리 배열로 변환하는 작업이 필요합니다.

문제 상황 이해하기

JSON 배열의 각 항목은 다음과 같은 속성을 가지고 있습니다.

id — 각 노드를 식별하는 고유한 값
parentId — 부모 노드의 id (루트 노드일 경우 0)
level — 트리 내에서의 깊이(단계)

입력 데이터는 이미 정렬되어 있다고 가정합니다. 즉, 어떤 항목 위에는 반드시 부모 노드 또는 형제(sibling) 노드가 존재하고, 아래에는 자식 노드 또는 형제 노드가 위치합니다.

입력 배열

const arr = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": null
    },
    {
        "id": "6",
        "parentId": "12",
        "text": "Boy",
        "level": "2",
        "children": null
    },
    {
        "id": "7",
        "parentId": "12",
        "text": "Other",
        "level": "2",
        "children": null
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": null
    },
    {
        "id": "11",
        "parentId": "9",
        "text": "Girl",
        "level": "2",
        "children": null
    }
];

기대하는 출력 결과

변환 후에는 각 부모 노드의 children 속성 안에 해당하는 자식 노드들이 중첩된 형태가 되어야 합니다.

const output = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": [
            {
                "id": "6",
                "parentId": "12",
                "text": "Boy",
                "level": "2",
                "children": []
            },
            {
                "id": "7",
                "parentId": "12",
                "text": "Other",
                "level": "2",
                "children": []
            }
        ]
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": [
            {
                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": []
            }
        ]
    }
];

해결 방법: 해시 맵(Map) 활용

가장 효율적인 접근 방식은 해시 맵을 이용하는 것입니다. 먼저 모든 노드를 한 번 순회하면서 id와 인덱스를 매핑하고, children을 빈 배열로 초기화합니다. 그다음 두 번째 순회에서 각 노드의 parentId를 확인하여, 부모가 있는 노드는 부모의 children에 추가하고, 루트 노드(parentId가 "0")는 결과 배열에 직접 담습니다.

이 방식은 시간 복잡도 O(n)으로 단 두 번의 순회만으로 변환이 완료되므로, 재귀 호출 없이도 대용량 데이터를 빠르게 처리할 수 있다는 장점이 있습니다.

예제 코드

const arr = [
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": null
    },
    {
        "id": "6",
        "parentId": "12",
        "text": "Boy",
        "level": "2",
        "children": null
    },
    {
        "id": "7",
        "parentId": "12",
        "text": "Other",
        "level": "2",
        "children": null
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": null
    },
    {
        "id": "11",
        "parentId": "9",
        "text": "Girl",
        "level": "2",
        "children": null
    }
];
const listToTree = (arr = []) => {
    let map = {}, node, res = [], i;
    for (i = 0; i < arr.length; i += 1) {
        map[arr[i].id] = i;
        arr[i].children = [];
    };
    for (i = 0; i < arr.length; i += 1) {
        node = arr[i];
        if (node.parentId !== "0") {
            arr[map[node.parentId]].children.push(node);
        }
        else {
            res.push(node);
        };
    };
    return res;
};
console.log(JSON.stringify(listToTree(arr), undefined, 4));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[
    {
        "id": "12",
        "parentId": "0",
        "text": "Man",
        "level": "1",
        "children": [
            {
                "id": "6",
                "parentId": "12",
                "text": "Boy",
                "level": "2",
                "children": []
            },
            {
                "id": "7",
                "parentId": "12",
                "text": "Other",
                "level": "2",
                "children": []
            }
        ]
    },
    {
        "id": "9",
        "parentId": "0",
        "text": "Woman",
        "level": "1",
        "children": [
            {
                "id": "11",
                "parentId": "9",
                "text": "Girl",
                "level": "2",
                "children": []
            }
        ]
    }
]

정리

평면 배열을 트리 구조로 변환할 때는 해시 맵을 활용한 두 단계 순회 방식이 가장 간단하고 효율적입니다. 객체 참조 특성 덕분에 원본 배열 내 노드에 자식을 추가하면 결과 배열에도 동일하게 반영됩니다. 데이터가 정렬되어 있지 않은 경우에도 이 방법은 정상적으로 동작하므로, 실무에서 널리 사용되는 패턴입니다.