Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

131
Visualizações
Returning Array from Recursive Binary Tree Search

Hi I've made a simple Binary Tree and added a pre-order traversal method. After throwing around some ideas I got stuck on finding a way to return each value from the traverse_pre() method in an array.

class BST:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        print(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre()

How would I modify the traverse_pre() function to return an array consisting of the node values. Is there a good example of this process for me to understand this further, I'm a bit stuck on how values can be appended to an array within recursion.

over 4 years ago · Santiago Trujillo
4 Respostas
Responde à pergunta

0

Here is how I would do it - all branches return their lists of subelements.

In case a node has no subelements, it only returns its own value. Otherwise, it also contains elements from the children.

Extend adds all elements from the child node result list to the parent node result list.

class BST:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        results = []

        if self.left:
            results.extend(self.left.traverse_pre())

        results.append(self.value)

        if self.right:
            results.extend(self.right.traverse_pre())

        return results


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

print(Tree.traverse_pre())
over 4 years ago · Santiago Trujillo Relatório

0

You can use an array as a global variable and in the traverse_pre() function you can append the value to that array, instead of print it out.

arr = []
class BST:
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None

    def add_child(self, val):
        if self.value:
            if val < self.value:
                if self.left == None:
                    self.left = BST(val)
                else:
                    self.left.add_child(val)
            else:
                if val > self.value:
                    if self.right == None:
                        self.right = BST(val)
                    else:
                        self.right.add_child(val)
        else:
            self.value = val

    def traverse_pre(self):
        if self.left:
            self.left.traverse_pre()
        arr.append(self.value)

        if self.right:
            self.right.traverse_pre()


Tree = BST(5)
Tree.add_child(10)
Tree.add_child(8)
Tree.add_child(2)
Tree.add_child(4)
Tree.add_child(7)

Tree.traverse_pre() 
print(arr)
over 4 years ago · Santiago Trujillo Relatório

0

I would approach the problem like this:

def traverse_pre(self):
    rslt = [self.value]
    if self.left:
        rslt.extend(self.left.traverse_pre())

    if self.right:
        rslt.extend(self.right.traverse_pre())
over 4 years ago · Santiago Trujillo Relatório

0

I would not recommend copying the entire tree to an intermediate list using .append or .extend. Instead use yield which makes your tree iterable and capable of working directly with many built-in Python functions -

class BST:
    # ...
    def preorder(self):
        # value
        yield self.value
        # left
        if self.left: yield from self.left.preorder()
        # right
        if self.right: yield from self.right.preorder()

We can simply reorder the lines this to offer different traversals like inorder -

class BST:
    # ...
    def inorder(self):
        # left
        if self.left: yield from self.left.inorder()
        # value
        yield self.value
        # right
        if self.right: yield from self.right.inorder()

And postorder -

class BST:
    # ...
    def postorder(self):
        # left
        if self.left: yield from self.left.postorder()
        # right
        if self.right: yield from self.right.postorder()
        # value
        yield self.value

Usage of generators provides inversion of control. Rather than the traversal function deciding what happens to each node, the the caller is left with the decision on what to do. If a list is indeed the desired target, simply use list -

list(mytree.preorder())
# => [ ... ]

That said, there's room for improvement with the rest of your code. There's no need to mutate nodes and tangle self context and recursive methods within your BST class directly. A functional approach with a thin class wrapper will make it easier for you to grow the functionality of your tree. For more information on this technique, see this related Q&A.

If you need to facilitate trees of significant size, a different traversal technique may be required. Just ask in the comments and someone can help you find what you are looking for.

over 4 years ago · Santiago Trujillo Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda