Binary tree from a list

[dan789]

Hi all,

I need to create a binary tree, whose data are stored in a list:

[[parent1, one_of_children_from_1],[parent2, one_of_children_from_2],[parent1, one_of_children_from_1],...]   #they are in random order

Can you give me any hint, what should I use in order to create such a binary tree?

[ichabod801]

Well, you could implement it as a list, with some appropriate functions. I would go for a class implementation, however. Binary trees are a common programming structure, so there is lots of information about them online.

[dan789]

Well, I'm using a class already, but I need some hint in the aspect of logic - how to create it? I was already thinking about using a queue, could this be useful in my case?

[ichabod801]

I would use a dictionary of values to node instances. Then as you go through the list you know which values already have nodes, and what nodes you need to create/join.

[dan789]

So, actually, I can create this tree in a way, where I create a lot of "subtrees" and then while iterating in a list just joining them, right?

[ichabod801]

Yeah. Each node has two children, which are None or another node. First you get A as the parent of B, make nodes A and B, with B as a child of A. Then you get C as the parent of D, do the same thing. When you get B as the parent of C, you know from your dictionary that you already have a B node and a C node, so you make the existing C node the child of the existing B node.

[dan789]

Well, I get this logic, but here I meet with the following trouble:

dictionary = {parent1 : (1child1, 1child2),parent3 : (3child1, 3child2),parent2 : (2child1, 2child2),...}
self.root = self.Node(head)   # I already have a algorithm to find a head of the whole tree
parents = list(dictionary)
p = 0
while (p != len(parents)-1):
      # --- here I want to write a described algorithm, but I´m not sure if the system of curr_node is right
      # ... it doesn´t create the right connection between nodes
      curr_node = self.Node(parents[p], self.Node(dictionary.get(parents[p])[0]),self.Node(dictionary.get(parents[p])[1]))
      p += 1

[ichabod801]

No, the dictionary starts empty. You have no head at the beginning. Taking the list from your original post as data:

nodes = {}
for parent, child in data:
    if parent not in nodes:
        nodes[parent] = Node(parent)
    if child not in nodes:
        nodes[child] = Node(child)
    # join nodes[parent] to node[child]
# Figure out head

[dan789]

Thanks, that works (I also added following lines of code).

Now I met with one another trouble; I shouldn´t use a self attribute whenever in that class (except self.root). I need to use dictionary "nodes" also in other method, can you give me any hint, how to "transport" this dictionary there, without making an attribute from that?

[ichabod801]

I don't understand the question. Why can't you use self? What method needs the dictionary? It would help if I could see the code for you nodes/tree.