Mirroring a Generic Tree - What's my mistake?

Question

I'm dealing with a Generic Tree I'm representing in this way:

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

And I have to mirror it, and recursion is allowed. I solved it in this way:

def mirror(self):
        """ Modifies this tree by mirroring it, that is, reverses the order
            of all children of this node and of all its descendants
            
            - MUST work in O(n) where n is the number of nodes
            - MUST change the order of nodes, NOT the data (so don't touch the data !)
            - DON'T create new nodes            
            - It is acceptable to use a recursive method.
                    
            
            Example:
            
            a     <-    Becomes:    a
            ├b                      ├i
            │├c                     ├e
            │└d                     │├h
            ├e                      │├g
            │├f                     │└f 
            │├g                     └b
            │└h                      ├d
            └i                       └c
            
              
        """
        mylist=[] #Initializing a list
        if self._child: #If GenTree has children:
            current=self._child #initalizing the variable for the while loop
            while current: #until there are root's sons
                mylist.append(current) #I put it them in the list
                current=current._sibling #Going ahead to put all the sons in the list
            self._child=mylist[-1] #The _child is now the "rightest" one, i.e. the son that points to None
            #Now I iterate within the list in the opposite direction:

            for i in range(-len(mylist),0):
                mylist[i]._sibling=mylist[i+1] if i<-1 else None #I go from right to left #and I reverse in this way the sense of the list (if the sons were ROOT|->a->b->c, now they should be ROOT|->c->b->a
            for i in range(-len(mylist),0):
                mylist[i].mirror() #Doing the recursion for each son using them as roots

But It's not working: Here's an example of an error generated by my code:

AssertionError: Children sizes are different !

ACTUAL    EXPECTED
a         a
├b        ├b
│└d       │├d          <--- DIFFERENT !
└e        │└c
          └e

What am I doing wrong?

user_7755665 · Answer

Consider the following:

for i in range(-1, -10, -1):
  print(i)
-1                                                                     
-2
-3
-4
-5
-6
-7
-8
-9

This is what you want to do if you intend to reverse the siblings in the list, but what you are doing is to start from -9 and go to -1, which is from the beginning of the list to its end.

So, the sibling of the node at -1 becomes the node at -2, etc. up until the sibling for element at 0 or -len(mylist) becomes None.

Change your loop as follows:

            for i in range(-1, -len(mylist), -1):
                mylist[i]._sibling=mylist[i-1]
            mylist[0]._sibling = None

To avoid all of the hassle of negative indexing you can also reverse your list and index it from the start as follows:

            mylist.reverse()
            for i in range(len(mylist)-1):
              mylist[i]._sibling = mylist[i+1]
            mylist[-1]._sibling = None

user_5459839 · Answer

As others explained, you are still accessing the list items in their original order, even when using negative indexes.

Still, I'd like to point out that such code challenges are intended for you to not use a standard list as helper, but to solve this without using such auxiliary data structure.

You can reverse a linked list by traversing it with 3 references, one lagging behind the other, and another leading in front of it. In Python, you can even do it with 2 references and tuple assignment.

As the siblings structure is essentially a linked list, you can use that approach:

    def mirror(self):
        # Reverse linked list of siblings
        prev = None
        current = self._child
        while current:
            current.mirror()  # Recursion
            # Create backwards link and move forward
            current._sibling, prev, current = prev, current, current._sibling
        self._child = prev

Mirroring a Generic Tree - What's my mistake?

2 Answers