# Python Binary Tree Iterator - Why Returned Node Becomes None?

## 14 April 2019 - 1 answer

I'm scratching my head for an hour.

I implemented binary tree in-order traversal using the iterator & stack.

``````class Node:
def __init__(self, val, left, right):
self.val = val
self.left = left
self.right = right

class BTIterator:
def __init__(self, root):
self.stack = []  # Use a list as a stack by using pop() & append()
self.root = root
self.leftmost = None

def Run(self):
node = self.root
while (node.left != None):
self.stack.append(node)
node = node.left
print(self.stack)
self.leftmost = node
print(self.leftmost.val)
while (self.Next(node) != None):
node = self.Next(node)
print(node.val)

def Next(self, node):
if (node.left != None):
while (node.left != None):
self.stack.append(node.left)
node = node.left
return node

elif (node.right != None):
node = node.right
while (node.left != None):
self.stack.append(node)
node = node.left
return node

else:
if self.stack != []:
node = self.stack.pop()
node.left = None
return node
``````
``````if __name__ == '__main__':
# Let's construct the tree.
n12 = Node(12, None, None)
n11 = Node(11, None, n12)
n9 = Node(9, None, None)
n10 = Node(10, n9, n11)
n15 = Node(15, None, None)
n13 = Node(13, n10, n15)
n5 = Node(5, None, None)
n3 = Node(3, None, n5)
n7 = Node(7, n3, n13)

bti = BTIterator(n7)
bti.Run()
``````

I also ran above implementation on IDE. From debugging, I clearly see `def Next(self, node)` returns `n7`. However once `node = self.Next(node)` line gets the `n7`, it turns `n7` into `None`. Why?!

I think this must be a python syntax that I do not know. Any pointer will be appreciated.

in your implementation, there are three problems I want to point out:

1. the main problem is your implemtation in `Next` is incorrect. Because inorder traversal is `left->root->right`, `if (node.left != None):` part is correct, but here:
``````        elif (node.right != None):
node = node.right
while (node.left != None):
self.stack.append(node)
node = node.left
return node
``````

you should return node itself first before deal with `right` child.

``````        else:
if self.stack != []:
node = self.stack.pop()
node.left = None
return node
``````

and you should not only `pop` when node is leaf, you should push every node in stack, and pop every `Next`.

1. you can not put `Next` in both while condition and block, because it will call twice.
``````while (self.Next(node) != None):
node = self.Next(node)
``````
1. `!= None` in `if (node.left != None):` is not needed in python, you can just use `if node.left:`

because `Next` has many problems, so I have to rewrited `Next`, here is the version I edited based on your code, and I have commented in details:

``````class BTIterator:
def __init__(self, root):
self.stack = []  # Use a list as a stack by using pop() & append()
self.root = root

def Run(self):
# find the left most node, which means then first node
node = self.root
while node.left:
self.stack.append(node)
node = node.left

# start from left most node
while node:
print(node.val)
node = self.Next(node)

def Next(self, node):
# find right node, if it is none, it's ok, we will deal with it afterwards
node = node.right

# reach the end
if not self.stack and not node:
return None

# push left child iteratively
while node:
self.stack.append(node)
node = node.left

# this is next node we want
return self.stack.pop()
``````

Hope that helps you, and comment if you have further questions. : )