CODEWITHSUNDEEP
pythondata-structurestree
geekidharsh
geekidharsh

Reputation: 3589

Recursive function failing while inorder traverse in tree ds

I am trying to implement tree data structure but I am stuck and having trouble understanding how to create a recursive function for inorder traversal for my binary tree.

This is what i have done so far: 

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



    def inorder_traversal(self):
        if self.node != None:
            return inorder_traversal(self.node.left)
            return self.node
            return inorder_traversal(self.node.right)

I don't seem to understand what's wrong.

Test inputs:

root = Node(1)
root.left = Node(3)
root.right = Node(4)

Error: 

File "trees-implementation.py", line 23, in inorder_traversal
    return inorder_traversal(self.node.left)
NameError: name 'inorder_traversal' is not defined

Upvotes: 0

Views: 93

Answers (2)

Coincoin14
Coincoin14

Reputation: 95

First, could you check if when you have your object, you don't put a parameter in

root = Node()

Then are you sure you can have several returns in your inorder_traversal() function ? Finally, the function is in the class Node() so if you call it try to add self.yourfunction

Upvotes: 0

cs95
cs95

Reputation: 402493

It looks like you've defined your traversal functions with respect to the Node. Does this make sense to you?

You should define a traversal with respect to the Tree, not the Node. The Node does not know it belongs to the tree, it's a dumb object.

Define the node.

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

Define the tree. Also define your traversal methods here.

class Tree:
    def __init__(self, root=None):
        self.root = root

    def inorder_traversal(self):
        def _inorder(root):
            if root != None:
                yield from _inorder(root.left)
                yield root.value
                yield from _inorder(root.right)

        return list(_inorder(self.root))

Initialise the tree with a root, and then traverse it.

tree = Tree(root)
tree.inorder_traversal()
[3, 1, 4]

Upvotes: 2

Related Questions