CODEWITHSUNDEEP
pythonpython-3.xbinary-tree
Jackie
Jackie

Reputation: 145

Creating a Binary Tree from string input

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.

Upvotes: 0

Views: 2708

Answers (1)

AChampion
AChampion

Reputation: 30258

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]]

Upvotes: 1

Related Questions