Create Binary Tree From List Of Lists In Python

I need to create a binary tree from a list of lists. My problem is that some of the nodes overlap(in the sense that the left child of one is the right of the other) and I want to s

Solution 1:

Here comes a solution that return you a Node object having left and right child allowing you to use most of the tree parsing algorithms. If needed you can easily add reference to the parent node.

data2 = [[1,2,3],
         [0,4,5],
         [0,0,6]]

def exceptFirstColumn(data):
    if data and data[0] :
        return [ row[1:] for row in data ]
    else :
        return []

def exceptFirstLine(data):
    if data :
        return data[1:]

def left(data):
    """ Returns the part of the data use to build the left subTree """
    return exceptFirstColumn(data)

def right(data):
    """ Returns the part of the data used to build the right subtree """
    return exceptFirstColumn(exceptFirstLine(data))
class Node():
    def __init__(self, value):
        self.value = value

        self.leftChild = None
        self.rightChild= None

    def __repr__(self):
        if self.leftChild != None and self.rightChild != None :
            return "[{0} (L:{1} | R:{2}]".format(self.value, self.leftChild.__repr__(), self.rightChild.__repr__())
        else:
            return "[{0}]".format(self.value)

def fromData2Tree(data):    
    if data and data[0] :
        node = Node(data[0][0])

        node.leftChild = fromData2Tree(left(data))
        node.rightChild= fromData2Tree(right(data))

        return node

    else :
        return None

tree = fromData2Tree(data2)
print(tree)

This code give the following result :

[1 (L:[2 (L:[3] | R:[5]] | R:[4 (L:[5] | R:[6]]]

That is the requested following tree. Test it on your data, it works. Now try to understand how it works ;)

   +-----1-----+
   |           |
+--2--+     +--4--+
|     |     |     |
3     5     5     6