CODEWITHSUNDEEP
pythonpython-3.xrecursiontuples
OmO Walker
OmO Walker

Reputation: 646

Returning string creates Tuple Python recursion

I have a recursive method in Python. Not sure if it helps but it checks how unbalanced AVL tree is. For example 10,20,30 is 'rr', 30,20,10 is 'll', 10,20,15 is 'rl' and 20,10,15 is 'lr'.
Here is my code:

def rotation_type(bst, ptr='dummy'):
    if ptr == 'dummy':
        ptr = bst.root
    if ptr.left != None or ptr.right != None:
        if ptr.left != None:
            return 'l', rotation_type(bst,ptr.left)
        else:
            return 'r', rotation_type(bst,ptr.right)

My code works and all but it returns a Tuple. For example if my binary tree is [10,20,30] it returns ('r', ('r', None)). Is there a way to return only a string like 'rr'? Sorry if this question has been asked before but I couldn't find it anywhere. Thanks in advance

Upvotes: 2

Views: 217

Answers (2)

Martijn Pieters
Martijn Pieters

Reputation: 1121584

You need to concatenate the recursive result, so you return a string each time:

return 'l' + rotation_type(bst, ptr.left)

Further remarks:

  • Use <something> is None and <something> is not None to test for None values; None is a singleton.

  • I'd use None as a default value rather than a string in your signature.

  • None is a falsey value, you could just use if ptr.left and if ptr.right.

  • You need to return something for the case where both children are missing.

Improved version:

def rotation_type(bst, ptr=None):
    ptr = ptr or bst.root
    if ptr.left:
        return 'l' + rotation_type(bst, ptr.left)
    elif ptr.right:
        return 'r' + rotation_type(bst, ptr.right)
    else:
        return ''

Upvotes: 3

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

Yes, an easy fix is to use string concatenation + over tuples ,:

def rotation_type(bst, ptr='dummy'):
    if ptr == 'dummy':
        ptr = bst.root
    if ptr.left != None or ptr.right != None:
        if ptr.left != None:
            return 'l' + rotation_type(bst,ptr.left)
        else:
            return 'r' + rotation_type(bst,ptr.right)
    return ''

You also have to return the empty string if nothing is returned (last line), since otherwise we will concatenate a string with a None-type, which will error.

I would also advice to use None over dummy, since this is usually the placeholder, instead there are really good reasons not to:

def rotation_type(bst, ptr=None):
    if ptr is None:
        ptr = bst.root
    if ptr.left != None or ptr.right != None:
        if ptr.left != None:
            return 'l' + rotation_type(bst,ptr.left)
        else:
            return 'r' + rotation_type(bst,ptr.right)
    return ''

You can still improve the code, but I leave this as an exercise.

Upvotes: 3

Related Questions