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

  expression-trees, list, python, tree

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!

Source: Python Questions

LEAVE A COMMENT