Python Binary Tree Iterator - Why Returned Node Becomes None?

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.

2. 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)

3. != 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. : )