Binary Tree: List of List to Nodes and Reference with Recursion

Question

I have been trying to convert a list of lists format to a binary tree object which consists of nodes and references. So far, I have a 3 cases where the left and right node is empty, left is empty and right is empty. The problem is that whenever I test my function, the recursion does not work. By that I mean the recursion depth is only one level before it returns the converted binary tree.

argument =  ['a', ['b', ['d', None, None],['f', None, None]], ['c', None, ['h', None, None]]]

def linkedlisttobinarytree (l):
    '''
    list of lists -> (nodes and references)
    Takes a list of lists and returns a binary tree in nodes and references form
    '''
    bt = BinaryTree(l[0])
    if (l[1] and l[2]) == None:
        return bt.getRootValue()
    elif l[1] != None and l[2] == None:
        bt.left = ll2nr(l[1])
    elif l[2] != None and l[1] == None:
        bt.right = ll2nr(l[2])
    return bt

For example, when I send the variable 'argument' into my method, it only yields 'a' as the root node and only 'a', the method only converts the first element in 'argument'. Can someone clarify why my the recursion depth is so shallow?

You havent posted BinaryTree code. SO users are out of crystal balls ;) probably - because Your l[1] and l[2] are None? Or one of those is None ? — brainovergrow, Mar 04 '15 at 21:23
Few small comments on your code: 1) the [accepted standard](http://stackoverflow.com/questions/3257919/is-none-vs-none) in Python to test if something is `None` is `is None` and not `== None`. 2) Python is not Java, so just [use attributes](http://stackoverflow.com/questions/6618002/python-property-versus-getters-and-setters) instead of boiler-plate get and set methods, unless you really need them. — Bas Swinckels, Mar 04 '15 at 21:50

score 0 · Accepted Answer · edited Jul 22 '22 at 09:48

I think that is because you didn't define the action when l[1] and l[2] are not none. So when you pass the argument to the function, it puts 'a' to the key of root, and find that none of the conditions defined matched, then the function exists without doing any thing. Therefore the return value contains only 'a' . Try this:

if (l[1] and l[2]) == None:
        return bt.getRootValue()
    elif l[1] != None and l[2] == None:
        bt.left = ll2nr(l[1])
    elif l[2] != None and l[1] == None:
        bt.right = ll2nr(l[2])
    else:
        bt.left = ll2nr(l[1])
        bt.right = ll2nr(l[2])

brainovergrow · Answer 2 · 2015-03-04T22:56:14.300

Checking Your function:

(...)
elif l[1] != None and l[2] == None:
    bt.left = ll2nr(l[1])
elif l[2] != None and l[1] == None:
    bt.right = ll2nr(l[2])

You can easily see adding print (l[1], l[2]) in place of dots, that neither of those conditions are fullfilled.

l[1] == ['b', ['d', None, None], ['f', None, None]]
and
l[2] == ['c', None, ['h', None, None]]

So, first condition is true and false ==> false and second condition also is true and false ==> false. Thus function returns bt.

If You change it to something like

if l[1] != None: # You might simply write "if l[1]:" as well...
    bt.left = ll2nr(l[1])
if l[2]:         # ...like this
    bt.right = ll2nr(l[2])

it might work better.

I changed Your function like this:

def make_tree(l):
    bt = BinaryTree(l[0])
    #if (l[1] and l[2]) == None:
    #    return bt.getRootValue()
    if l[1]:
        bt.left = make_tree(l[1])
    if l[2]:
        bt.right = make_tree(l[2])
    if not l[1] and not l[2]:
        bt.left = "*"
        bt.right = "*"
    return bt

def printer(node, depth=0):
    indent = '\t' * depth
    if node:
        if isinstance(node, basestring):
            print ("{}{}={}".format(indent, node, depth))
        else:
            print ("{}{}={}".format(indent, node.key, depth))
            printer(node.left, depth + 1)
            printer(node.right, depth + 1)
    else:
        print ("{}*={}".format(indent, depth))

and got nice printout:

Oh right, so I should add another case where I can process l[1] and l[2] — Joseph Lee, Mar 04 '15 at 21:54

Binary Tree: List of List to Nodes and Reference with Recursion

2 Answers2