Какой алгоритм применить для построения вложенного дерева?

Question

[netz-sanya]

Есть Такой массив:

[{
    "Level": 0,
    "Val": "1"
}, {
    "Level": 0,
    "Val": "2"
}, {
    "Level": 1,
    "Val": "2.1"
}, {
    "Level": 1,
    "Val": "2.2"
}, {
    "Level": 2,
    "Val": "2.2.1"
}, {
    "Level": 3,
    "Val": "2.2.1.1"
}, {
    "Level": 0,
    "Val": "3"
}, {
    "Level": 1,
    "Val": "3.1"
}]

Нужно преобразовать в подобное дерево:

[{
    "Level": 0,
    "Val": "1",
    "Children": []
}, {
    "Level": 0,
    "Val": "2",
    "Children": [{
        "Level": 1,
        "Val": "2.1",
        "Children": []
    }, {
        "Level": 1,
        "Val": "2.2",
        "Children": [{
            "Level": 2,
            "Val": "2.2.1",
            "Children": [{
                "Level": 3,
                "Val": "2.2.1.1",
                "Children": []
            }]
        }]
    }]
}, {
    "Level": 0,
    "Val": "3",
    "Children": [{
        "Level": 1,
        "Val": "3.1",
        "Children": []
    }]
}]

Не могу сообразить как преобразовать.

Comments

[rustler2000]

А что, на ум приходит много вариантов?

[Павел Беляев]

где принадлежность к парент?

[d'Ivan]

Павел Беляев прав. Нельзя однозначно построить дерево без указания родителя узла.

Answer 1

[qqrm]

Возможно стоит использовать реализацию дерева по ссылке
https://godoc.org/github.com/erriapo/redblacktree