Tree. Delete node, but pass its children to a parent node-CodePudding

I'm trying to traverse an arbitrary tree and build a new tree, which would delete certain nodes, but connect their children to parent nodes. I don't want to use a recursion or classes, only lists, dictionaries, etc.

Below is the code that does half of the job - it traverses the original tree and tries to build a new tree, but I just can't wrap my mind around building a new tree using a stack.

original_tree = {
    'id': 1,
    'children': [
        {
            'id': 2,
            'children': [{'id': 3}, {'id': 4}]
        },
        {
            'id': 5,
            'children': [
                {'id': 6, 'children': [{'id': 7}]},
                {'id': 8, 'delete': True, 'children': [{'id': 9}, {'id': 10}]},
                {'id': 11}
            ]
        }
    ]
}

stack = [original_tree]
new_tree = {}

while len(stack):
    node = stack.pop(0)
    print(node['id'])
    children = node.get('children', [])

    # === Start building a new tree ===
    if not node.get('delete'):
        new_tree['id'] = node['id']
        pass
    # ================================

    for i in range(len(children) - 1, -1, -1): 
        stack.insert(0, children[i])

CodePudding user response：

Using a stack, you lose the link between parent and child — there's no way to know if the next item you pop off the stack is a sibling or parent. You can fix that by keep track of parents as you add items to the stack. Then when you pop an item from the stack you have a reference to the parent node.

To handle deletes, you only need to add the deleted children to the stack with the correct parent reference. Here's a quick example:

original_tree = {
    'id': 1,
    'children': [
        {
            'id': 2,
            'children': [{'id': 3}, {'id': 4}]
        },
        {
            'id': 5,
            'children': [
                {'id': 6, 'children': [{'id': 7}]},
                {'id': 8, 'delete': True, 'children': [{'id': 9}, {'id': 10}]},
                {'id': 11}
            ]
        }
    ]
}

stack = [{'parent': None, 'node':original_tree}]
root = None

while len(stack):
    frame = stack.pop()

    node = frame['node']
    parent = frame['parent']
    
    # Allocate a new node
    new_node = {'id': node['id']}
    
    # Append the node to the parent if there is one; there won't be one for the root
    if parent is not None:
        parent.setdefault('children',[]).append(new_node)
    else:
        root = new_node
        
    children = node.get('children', [])

    print(node['id'])

    for child in reversed(children): 
        if child.get('delete'):
            # to delete a child, you need to add its children to the stack
            grand_children = child.get('children', [])
            for grand_child in reversed(grand_children):
                stack.append({'parent': new_node, 'node':grand_child})
        else:
            stack.append({'parent': new_node, 'node':child})

Printing the new tree root gives you:

{'id': 1,
 'children': [{'id': 2, 'children': [{'id': 3}, {'id': 4}]},
  {'id': 5,
   'children': [{'id': 6, 'children': [{'id': 7}]},
    {'id': 9},
    {'id': 10},
    {'id': 11}]}]}

Where the children of deleted node 8 and now children of 5.

(also, with python lists, it's more efficient to pop and append off the end: pop() & append() rather than insert(0) and pop(0))