How to create a new N-ary ExpressionTree object from a list of nodes and leaves?

Code newbie here, and I am creating a project in Python.

I have a class called ExpressionTree which is, an N-ary expression tree, such that each node is not merely restricted to having only two children; it can have more than 2, but not less than 2.

The only operators I would use in this tree are "+" and "-" (but the code should work for any operator).

All leaves are either a single letter string, or an integer, and all parents are either "+" or "-".

The method I am trying to create is called create_tree, which takes in a list called lst, for which the type is: List[List[Union[int, str]]], and returns a successfully created ExpressionTree that was made from the parameter: lst.

Each list in lst represents a level, but for each operator in the list, the next lists are the children of each operator. For example, if lst = [[+], [+, +], [1, 2], [3, 4]], then the Tree should look something like:

Tree 1

On a more nested example, if I were to run create_class([[+], [3, +, +], [5, *], [b, c], [6, a]]), the Tree I should be getting is:

Tree 2

I know that a Queue would be very useful, but I do not know where to start. I don't think this code necessarily would need recursion, but it could work with it as well if implemented correctly. Any help with the code is immensely appreciated. Thanks in advance!

Solution

You can recursively partition the list to build the tree:

from collections import deque
def to_tree(d):
   k = [[i, [] if i not in {'+', '*'} else d.popleft()] for i in d.popleft()]
   for i in range(len(k)):
     if k[i][0] in {'+', '*'}: 
        d = deque([k[i][-1], *d])
        k[i][-1] = k[i][-1] if len(d) == 1 else to_tree(d)
   return [[a, b] if b else a for a, b in k]
   

lst = [['+'], ['+', '+'], ['1', '2'], ['3', '4']]
lst1 = [['+'], ['3', '+', '+'], ['5', '*'], ['b', 'c'], ['6', 'a']]
lst2 = [['+'], ['3', 'c', '+'], ['5', 'a']]
print(to_tree(deque(lst)))
print(to_tree(deque(lst1)))
print(to_tree(deque(lst2)))

Output:

[['+', [['+', ['1', '2']], ['+', ['3', '4']]]]]
[['+', ['3', ['+', ['5', ['*', ['6', 'a']]]], ['+', ['b', 'c']]]]]
[['+', ['3', 'c', ['+', ['5', 'a']]]]]