I solved an exercise where I had to apply a recursive algorithm to a tree that's so defined:

class GenericTree:
    """ A tree in which each node can have any number of children. 
    
        Each node is linked to its parent and to its immediate sibling on the right
    """
    
    def __init__(self, data):
        self._data = data
        self._child = None
        self._sibling = None
        self._parent = None  

I had to concatenate the data of the leaves with the data of the parents and so on until we arrive to the root that will have the sum of all the leaves data. I solved it in this way and it works but it seems very tortuous and mechanic:

    def marvelous(self):
        """ MODIFIES each node data replacing it with the concatenation 
            of its leaves data 
            
            - MUST USE a recursive solution
            - assume node data is always a string

        """
        if not self._child: #If there isn't any child
            self._data=self._data #the value remains the same
        if self._child: #If there are children
            if self._child._child: #if there are niece
                self._child.marvelous() #reapply the function to them
            else: #if not nieces
                self._data=self._child._data #initializing the name of our root node with the name of its 1st son
                #if there are other sons, we'll add them to the root name
                if self._child._sibling: #check
                    current=self._child._sibling #iterating through the sons-siblings line
                    while current: 
                        current.marvelous() #we reapplying the function to them to replacing them with their concatenation (bottom-up process)
                        self._data =current._data #we sum the sibling content to the node data
                        current=current._sibling #next for the iteration
            #To add the new names to the new root node name:
            self._data="" #initializing the root str value
            current=self._child #having the child that through recursion have the correct str values, i can sum all them to the root node
            while current:
                self._data =current._data
                current=current._sibling
        if self._sibling: #if there are siblings, they need to go through the function themselves
            self._sibling.marvelous()

Basically I check if the node tree passed has children: if not, it remains with the same data. If there are children, I check if there are nieces: in this case I restart the algorithm until I can some the leaves to the pre-terminal nodes, and I sum the leaves values to put that sum to their parents'data. Then, I act on the root node with the code after the first while loop, so to put its name as the sum of all the leaves. The final piece of code serves as to make the code ok for the siblings in each step. How can I improve it?

CodePudding user response：

It seems to me that your method performs a lot of redundant recursive calls.

For example this loop in your code:

                    while current: 
                        current.marvelous()
                        self._data  = current._data
                        current = current._sibling

is useless because the recursive call will be anyway performed by the last instruction in your method (self._sibling.marvelous()). Besides, you update self._data and then right after the loop you reset self._data to "".

I tried to simplify it and came up with this solution that seems to work.

    def marvelous(self):
        if self.child:
            self.child.marvelous()

            # at that point we know that the data for all the tree
            # rooted in self have been computed.  we collect these
            self.data = ""
            current = self.child
            while current:
                self.data  = current.data
                current = current.sibling

        if self.sibling:
            self.sibling.marvelous()

And here is a simpler solution:

    def marvelous2(self):
        if not self.child:
            result = self.data
        else:
            result = self.child.marvelous2()
            self.data = result
        if self.sibling:
            result  = self.sibling.marvelous2()
        return result

marvelous2 returns the data computed for a node and all its siblings. This avoids performing the while loop of the previous solution.