Как пробежаться по стуктуре данных и получить все вложенные id?

Question

[pcdesign]

Вот есть такая структура:

[
  {
    "id":1,
    "parent":""
  },
  {
    "id":2,
    "parent":1
  },
  {
    "id":3,
    "parent":1
  },
  {
    "id":4,
    "parent":3
  },
  {
    "id":5,
    "parent":3
  }
]

Как добавить список всех ID, которые являются вложенными, чтобы получилось вот так:

[
  {
    "id":1,
    "parent":"",
    "sub_ids": [2, 3, 4, 5]
  },
  {
    "id":2,
    "parent":1,
    "sub_ids": []
	
  },
  {
    "id":3,
    "parent":1,
    "sub_ids": [4, 5]	

  },
  {
    "id":4,
    "parent":3,
    "sub_ids": []
  },
  {
    "id":5,
    "parent":3,
    "sub_ids": []
  }
]

Answer 1

[pcdesign]

Вот решение с помощью рекурсии. Мне оно не нравится, но что-то другое я не могу придумать:

def get_sub_ids(parent, arr):
    for sub in my_list:
        if sub['parent'] == parent:
            arr.append(sub['id'])
            get_sub_ids(sub['id'], arr)

    return arr


for item in my_list:
    item['sub_ids'] = get_sub_ids(item['id'], [])

Результат:

[{'id': 1, 'parent': '', 'sub_ids': [2, 3, 4, 5]}, {'id': 2, 'parent': 1, 'sub_ids': []}, {'id': 3, 'parent': 1, 'sub_ids': [4, 5]}, {'id': 4, 'parent': 3, 'sub_ids': []}, {'id': 5, 'parent': 3, 'sub_ids': []}]

Answer 2

[Максим]

lst = [
  {
    "id":1,
    "parent":""
  },
  {
    "id":2,
    "parent":1
  },
  {
    "id":3,
    "parent":1
  },
  {
    "id":4,
    "parent":3
  },
  {
    "id":5,
    "parent":3
  }
]

for item in lst:
    item.update({'sub_ids': [sub['id'] for sub in lst if sub['parent'] == item['id']]})

print(lst)

Comments

[pcdesign]

Спасибо за ответ.
Но в этом случае получается только так:
{'id': 1, 'parent': '', 'sub_ids': [2, 3]}
А должно быть так:

{
    "id":1,
    "parent":"",
    "sub_ids": [2, 3, 4, 5]
  },

То есть ID не со всех уровней вложенности собираются.