Parse a list of flattened non-binary tree nodes

Question

I have a list of data whose elements are all structured like the following:

(node_id, parent_node_id, children_node_ids, data)

or, in other words, it's similar to this:

[(7, 2, [15, 23, 47], _data_), (15, 7, [64, 95, 123, 271, 272], _data_), ...]

so, the number of children per node is variable.

The 'root node' is the node whose parent_node_id is None, e.g.:

(2, None, [4, 7, 9, 11], _data_)

And, as seen in the example, the 'root node' is 'hidden' somewhere in the loooong list.

I don't know why it's structured that way, but I have to work with it.

How can I efficiently parse the above list into a non-binary tree?

My 'naive' approach is to create a custom non-binary tree class, then start populating it by searching for the root node, then searching for its children, then recursively search for the root's children's descendants...

But I wonder if there's a better way of doing it.

(One purpose is to create a graphical tree to allow visualization. Another is to sort the data so that lower-level nodes are always to the left of the higher-level nodes.)

ojii ojii · Accepted Answer · 2015-10-08T09:39:58

This is what I would do:

class Node(object):
    def __init__(self, node_id, data):
        self.node_id = node_id
        self.data = data
        self.children = []

    def add_child(self, child):
        self.children.append(child)


def build_tree(raw_nodes):
    root = None
    nodes = {
        node_id: Node(node_id, data)
        for node_id, _, __, data in raw_nodes
    }
    for node_id, parent_id, children, __ in raw_nodes:
        node = nodes[node_id]
        for child_id in children:
            node.add_child(nodes[child_id])
        if parent_id is None:
            if root is not None:
                raise ValueError("Multiple root nodes found")
            else:
                root = node
    if root is None:
        raise ValueError("No root found")
    return root

Parse a list of flattened non-binary tree nodes

1 Answers