CODEWITHSUNDEEP
pythonalgorithmbinary-treetree-traversal
Saurabh
Saurabh

Reputation: 6920

Binary Tree Iterative Inorder Traversal

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?

Upvotes: 1

Views: 544

Answers (2)

Vikash Madhow
Vikash Madhow

Reputation: 1344

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

Upvotes: -1

Julien
Julien

Reputation: 15071

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]

Upvotes: 2

Related Questions