Tree Inorder Traversal Python

Question

I'm trying to add elements to a binary tree and print them in in-order.

I'm getting an error while adding an element: AttributeError: 'NoneType' object has no attribute 'left'

Please let me know where I have to make a change Below is the code

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

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)

        else:
            self.data = data

    def InorderTraversal(self):
        if self.data is None:
            return
        self.left.InorderTraversal()
        print(self.data)
        self.right.InorderTraversal()



if __name__ == "__main__":
    root = Node(1)
    root.insert(2)
    root.insert(3)
    root.insert(4)
    root.InorderTraversal()

I am Implementing Trees First time Doesn't Have any idea

The data attribute should not affect the structure of your tree at all. — chepner
– chepner, Commented Sep 20, 2022 at 19:43

rdas · Accepted Answer · 2022-09-20 18:12:11Z

1

You should check if a node has left & right children before recursing on them:

class Node:

   ...
   def InorderTraversal(self):
        if self.left:  # if left child exists, then recurse on it
            self.left.InorderTraversal()
        print(self.data)
        if self.right:  # if right child exists, then recurse on it
            self.right.InorderTraversal()

Result:

answered Sep 20, 2022 at 18:12

rdas

21.4k6 gold badges39 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

sl0wcoder · Accepted Answer · 2022-09-20 19:24:34Z

You need the Node to be a separate class which will be used by the Tree class.
The insert and inorder_traversals are operations you do on a tree and not on a node. This is kinda the first thing you should do.

There are already pretty good resources you can look at since I might not be able to explain in that kind of detail : https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Also, you need to read up a little on how recursion and the classes work in python as I see some mistakes that can be fixed.
You're recursively printing the inorder traversal but you're doing the checks on self.data and running on self.left and self.right . self is pointing to the same data and you need to pass the node you wanna process next in the recursive function.
Also, you need to check the None condition on the Node and not on the data. Basically the node doesn't exist and that means you've to return from there

The inorder code overall idea is correct but you're working with wrong variables and basically you'll end up with incorrect output (or infinite loop)

My suggestion is to read up some more on tree on geeksforgeeks to begin with!

Collectives™ on Stack Overflow

Tree Inorder Traversal Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related