Creating a Binary Tree from string input

Question

I'm trying to create a recursive (or looping) function that takes a string as input, formate "(2(1)(3))" (i'm not worried about sorting it) and interprets it as a list into a binary tree such as [2[1 [] []][3 [] []]] to be simple. Here is what I've worked out so far, but it isn't working. Here is what I've got so far:

def subtrees(string):
    tree = []
    for x in string:
        if x == "(":
            return tree.append(subtrees(string[1:]))
        elif x == ")":
            return tree
        else:
            tree.append(int(x))
            return tree.append(subtrees(string[1:]))

After extensive testing, I've found two big errors: one being that the return after it finds the first closed parentheses finishes the entire running function (rather than just that one recursive call to end a node), and for some reason when I try to print the output it prints None. Any help/hints would be appreciated, as I'm really pretty lost here.

AChampion · Accepted Answer · 2016-03-26 02:42:23Z

1

You have a number of issues with your function:

list.append() returns None
you are returning for every condition (usually None because of above)
your are unneccessarily recursing for an element
your recursive functions do not advance your outer functions because you are passing in a copy of the string, turn the string into an iterable

Quick fixes:

def subtrees(string):
    s = iter(string)
    tree = []
    for x in s:
        if x == "(":
            tree.append(subtrees(s))
        elif x == ")":
            return tree
        else:
            tree.append(int(x))
    return tree[0]

>>> subtrees('(2(1)(3))')
[2, [1], [3]]

answered Mar 26, 2016 at 2:42

AChampion

30.4k4 gold badges63 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

patito Over a year ago

I know this is an old question, but is there any way to parse this type of input into a binary tree? like class Tree():left, right, value?

Collectives™ on Stack Overflow

Creating a Binary Tree from string input

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related