This was a question in a cs exam I wrote a few months ago and scored zero points in. We have a binary tree structure built as follows:

class Tree:
    def __init__(self,left=None, value=None, right=None):
        if value == None or left == None or right == None:
            self.empty = True
        else:
            self.empty = False
            self.value = value
            self.left = left
            self.right = right

Then a function for extracting the values from the tree and pouring them into a list was given:

def to_list(self):
        if self.empty:
            return []
        else:
            ll = self.left.to_list()
            lr = self.right.to_list()
            return ll   [self.value]   lr

Importantly - This function retains the order of elements as it was represented in the tree.

The task then was to write an iterative version of this "to_list" function that also retains this structure.

I have since written a functioning version but it is painfully bad so I'd like the input of more knowledgeable programmers.

Here is my version:

def to_list_iter(self):
        stack = []
        if self.empty:
            return []
        else:
            stack.append(self)
            while True:
                for x in range(len(stack)):
                    if type(stack[x]) != int:
                        middle = stack[x]
                        if middle.empty == False:
                            stack[x] = middle.value
                            stack.insert(x,middle.left)
                            stack.insert(x 2,middle.right)
                        else:
                            stack[x] = 0
                                
                check = True
                for z in stack:
                    if type(z) != int:
                        check = False
                if check == True:
                    return list(filter(lambda a: a != 0, stack))

CodePudding user response：

To be honest, I don't fully understand how your method works... it seems to work, but it's certainly a bit complicated. And the two for loops within the while look like O(n²), maybe even O(n³) due to those insert bits within the loop, whereas an O(n) algorithm is possible.

Basically, you can convert your recursion to a DFS-loop on a stack with mixed elements: Tree nodes and values (int, or any type other than Tree). Starting with self on the stack, you check the top element on the stack:

• If it's a Tree node, and if it's not empty, put the right, then value, then left onto the stack, in that order; if it is empty, just skip it
• if it is any other type, it must be a value, so add it to the result list

This works, since you put the left branch onto the stack last, so it's the next one you pop, thus descending into the left-most branch, then adding the value of that, then continuing with the right branch of that, and so on, until you end in the right-most branch at the very bottom of the stack.

In code, this may look somewhat like this:

def to_list_iter(self):
    result = []
    stack = [self]
    while stack:
        node = stack.pop()
        if isinstance(node, Tree):
            if not node.empty:
                stack.append(node.right)
                stack.append(node.value)
                stack.append(node.left)
        else:
            result.append(node)
    return result