Binary Tree Iterative Inorder Traversal

Question

I'm trying to implement an iterative inorder traversal of a binary tree.

node.py:

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

inorder_traversal.py:

from node import Node def in_order(root): stack = nodes = [] while stack or root: if root: stack.append(root) root = root.left else: current = stack.pop() nodes.append(current.node) root = current.right return nodes def main(): ''' Construct the below binary tree: 15 / \ / \ / \ 10 20 / \ / \ 8 12 16 25 ''' root = Node(15) root.left = Node(10) root.right = Node(20) root.left.left = Node(8) root.left.right = Node(12) root.right.left = Node(16) root.right.right = Node(25) print(in_order(root)) if __name__ == '__main__': main()

I've been getting: AttributeError: 'int' object has no attribute 'node'.

How can I resolve this error?

Please provide the expected MRE. Show where the intermediate results deviate from the ones you expect. We should be able to paste a single block of your code into file, run it, and reproduce your problem. This also lets us test any suggestions in your context. Give the entire error message, including the stack trace. We also expect that you will trace the offending values just before the point of error. Where are you confused about how they got to those values? — Prune
– Prune, Commented Nov 2, 2020 at 1:48
@Prune the example given here seems pretty minimal and reproducible to me... — Julien
– Julien, Commented Nov 2, 2020 at 1:51
@Prune Sorry I just added the import statement in the second code block. The stack trace had 3 lines in it which I felt would be unnecessary if added completely. — Saurabh
– Saurabh, Commented Nov 2, 2020 at 1:58

Julien · Accepted Answer · 2020-11-02 01:45:10Z

stack = nodes = [] creates two references to the same list object. When you do stack.append(root) or nodes.append(current.node) this affects both stack and nodes because they are the same. What you want is 2 different objects:

stack = [] nodes = []

Then you'll get this output: [8, 10, 12, 15, 16, 20, 25]

Vikash Madhow · Accepted Answer · 2020-11-02 01:58:53Z

The value of the node variable is initialized to an Int in your code (e.g. Node(5)) and your in_order method push that value on the stack and later pop it and try to access its node variable, which will result in the error.

Here's an implementation that does not have that error and uses recursion for the in order traversal (which can be simpler to follow).

class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def in_order(node): nodes = [] if node.left: nodes.extend(in_order(node.left)) nodes.append(node.value) if node.right: nodes.extend(in_order(node.right)) return nodes

Collectives™ on Stack Overflow

Binary Tree Iterative Inorder Traversal

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related