CODEWITHSUNDEEP
pythonalgorithmbinary-tree
p.ram
p.ram

Reputation: 109

List of all elements of Binary Tree

Being a beginner, I have been trying to implement Binary Tree in python. And have been available to implement a lot successfully with only one problem that I am unable to return a list of all the elements (traverse())in the binary tree. I am using two classes here, Node and BinaryTree.

Node Class

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

Traverse method to return all the elements in the binary tree.

    def traverse(self): #<-- Problem here
        tree_elements = []
        if self.left != None:
            self.left.traverse()

        tree_elements.append(self.value)

        #debug
        print(self.value, end=" ")

        if self.right != None:
            self.right.traverse()
        return tree_elements

    def addNode(self, node):
        if node.value < self.value and node.value != self.value:
            if self.left == None:
                self.left = node
            else:
                self.left.addNode(node)
        elif node.value > self.value and node.value != self.value:
            if self.right == None:
                self.right = node
            else:
                self.right.addNode(node)

    def search(self, val):
        if val == self.value:
            return "Found"

        elif val < self.value:
            if self.left != None:
                return self.left.search(val)
            else:
                return "Not Found "
        elif val > self.value:
            if self.right != None:
                return self.right.search(val)
            else:
                return "Not Found"

Binary Tree

class BinaryTree:
    def __init__(self):
        self.root = None

    def addVlaue(self, val):
        node = Node(val)
        if self.root == None:
            self.root = node
        else:
            self.root.addNode(node)

     def search(self, val):
         if self.root == None:
             return False
         else:
             return self.root.search(val)

    def traverse(self):
         if self.root == None:
             return "no data"
        else:
            return self.root.traverse()

Problem:

traverse method has to return all the elements in the binary tree, but i have been getting only first value of the tree.

example:

elements: 100 18 46 5 65 5 31 71 94 43 #input in the tree

output from tree: 5 18 31 43 46 65 71 94 100 #expected output

[100] #output from the tree

Upvotes: 0

Views: 1929

Answers (1)

jfaccioni
jfaccioni

Reputation: 7509

The tree_elements list needs to go along the recurvise calls, collecting each node along the way. In other words, it must be passed as an argument to traverse calls (except when calling traverse for the root node).

Otherwise a new list is created and discarded in each traverse call (since you never do anything with the return value of traverse during its recursion), except for the top recursive call which returns the root element only.

Try this implementation:

def traverse(self, tree_elements=None):
    if tree_elements is None:
        tree_elements = []
   if self.left != None:
        self.left.traverse(tree_elements=tree_elements)
    tree_elements.append(self.value)
    if self.right != None:
        self.right.traverse(tree_elements=tree_elements)
    return tree_elements

Upvotes: 3

Related Questions