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?

Answer 1

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]