Fix depth tree in Python

Question

I want to implement a tree structure which has fixed depth, i.e. when adding children to the leef nodes, the whole tree structure should "move up". This also means that several roots can exist simultaneously. See example beneath: In this example, the green nodes are added in iteration 1, deleting the top node (grey) and making the two blue nodes at K=0 and Iteration 1 root nodes.

How do I go about implementing this?

Answer 1

Store each node with a reference to its parent. When you add a node to it as a child, walk up the parents (from the node being added to) and delete the third one after you set the parent reference in all of its children to None. Then add the children of the deleted node to your list of trees.

class Node(object):

    depth = 4

    def __init__(self, parent, contents):
        self.parent = parent
        self.contents = contents
        self.children = []


def create_node(trees, parent, contents):
    """Adds a leaf to a specified node in the set of trees.

    Note that it has to have access to the container that holds all of the trees so
    that it can delete the appropriate parent node and add its children as independent 
    trees. Passing it in seems a little ugly. The container of trees could be a class
    with this as a method or you could use a global list. Or something completely
    different. The important thing is that if you don't delete every reference to the
    old root, you'll leak memory.
    """
    parent.children.append(Node(parent, contents))

    i = 0:
    L = Node.depth - 1
    while i < L:
        parent = parent.parent
        if not parent:
            break
        i += 1
    else:
        for node in parent.children:
            node.parent = None
        trees.extend(parent.children)
        i = trees.find(parent)
        del trees[i]