Creating the list that corresponds to the preorder path on binary trees-CodePudding

I was reading the following link. I want to create a method that instead of printing the elements, it returns the associated list. This is what I did:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self, root):
        self.root = Node(root)   

def preorder_sequence(self, current_node):
    """Helper method - use this to create a 
    recursive print solution."""
    s = []
    if current_node is not None:
        s.append(current_node.value)
        self.preorder_sequence(current_node.left)         
        self.preorder_sequence(current_node.right)

    return s

This method is just returning the root element.

CodePudding user response：

The main issue is that although your method returns a list, the recursive calls ignore that returned list, and so each call can only return a list that has at the most one element in it. Remember that s is a local name, and each execution context of your function has its own version of it. Your code really needs to capture the returned list as that is the only access the caller has to the list that the recursive execution created.

You could correct your code like this:

    def preorder_sequence(self, current_node):
        if current_node is not None:
            return ([current_node.value]
                      self.preorder_sequence(current_node.left)         
                      self.preorder_sequence(current_node.right))
        else:
            return []

Here you see how the lists that are created by the recursive calls are used to build a larger list (using ).

Now I should add that it is more pythonic to create a generator for this purpose: this means the function does not create a list, but just "spits out" the values in the requested order, and it becomes the responsibility of the caller to do something with them (like putting them in a list or printing them):

    def preorder_sequence(self, current_node):
        if current_node is not None:
            yield current_node.value
            yield from self.preorder_sequence(current_node.left)         
            yield from self.preorder_sequence(current_node.right)

I would even move the recursive part of this method to the Node class:

class Node:
    # ...

    def preorder_sequence(self):
        yield self.value
        if self.left:
            yield from self.left.preorder_sequence()
        if self.right:
            yield from self.right.preorder_sequence()

And then in the BinaryTree class it would become:

class BinaryTree:
    # ...

    def preorder_sequence(self):  # No more extra argument here
        if self.root:
            return self.root.preorder_sequence()

The caller can for instance do these things now:

tree = BST()
# ... populate the tree
# ...
# And finally create the list
lst = list(tree.preorder_sequence())

Or, just print using the * operator:

tree = BST()
# ... populate the tree
# ...
print(*tree.preorder_sequence())