1

I'd like to find the parent sibling in this array. 

arr = {
    'children': [
        {
            'id':'item_1',
            'title':'Item 1',
            'children': [
                {
                    'id':'item_a',
                    'title':'Item A'
                },
                {
                    'id':'item_b',
                    'title':'Item B'
                },
                {
                    'id':'item_c',
                    'title':'Item C',
                    'children': [
                        {
                            'id':'item_i',
                            'title':'Item I'
                        },
                        {
                            'id':'item_ii',
                            'title':'Item II'
                        }
                    ]
                }
            ]
        }
    ]
}

For instance if I put "item_b" into the method it must return "item_1" (ignoring "children" as a parent). Something similar to this:

>>> parent = get_parent(arr, 'item_i', ['children'])
>>> parent['id']
item_c
>>> parent = get_parent(arr, 'item_1', ['children'])
>>> parent['id']
None

My id's are unique, so I know there will only ever be one parent.

I've looked at examples by mgilson and Claudiu, but I can't get my head around how to change these to what I'm after. Claudius solution looks like the right direction, but with my array it just returns [].

Edit: ewcz solution works great. I modified it a bit to allow getting the title as well:

def get_parent(arr, item_id):
    L = [(None, arr)]
    while L:
        parent_item, item = L.pop()
        curr_id = item.get('id', None)
        if curr_id == item_id:
            return parent_item

        children = item.get('children', [])
        for child in children:
            L.append((item, child))

parent = get_parent(arr, 'item_i')
print(parent.get('id'))
print(parent.get('title'))
Community
  • 1
  • 1
NinjaFart
  • 1,626
  • 1
  • 20
  • 24
  • Are you sure about the "sibling" word in title? From the description it looks like you only want the parent items. Sibling items would be those that share a parent, like `item_i` and `item_ii` in your example. – gereleth Apr 23 '17 at 10:12
  • @gereleth You might be right, but I was thinking `id` and `title` are siblings to `children`. – NinjaFart Apr 23 '17 at 10:21
  • I recently learned about the a* algorithm and now I see that @ewcz code is very similar to the algorithm. Just thought this might help any googlers :) – NinjaFart Sep 17 '17 at 06:37

1 Answers1

1

one option would be to traverse your array and return the parent id as soon as the traversal hits the item of interest:

def get_parent(arr, item_id):
    L = [(None, arr)]
    while L:
        parent_id, item = L.pop()

        curr_id = item.get('id', None)
        if curr_id == item_id:
            return parent_id

        children = item.get('children', [])
        for child in children:
            L.append((curr_id, child))

parent = get_parent(arr, 'item_i')
ewcz
  • 12,819
  • 1
  • 25
  • 47