While loop versus If statement in Binary Search Tree BST traversals in Python-CodePudding

I am confused why a while loop is causing infinite recursion on a binary search tree Inorder traversal when I have put the terminating condition in the while loop

def Inorder(self, vals):
        while(self.left != None):
            print("Going left value seen = ",self.left.val)
            self.left.Inorder(vals)
        # if self.val is not None:
        vals.append(self.val)
        print("vals=",vals)
        if self.right is not None:
            print("Going right value seen = ",self.right.val)
            self.right.Inorder(vals)
        #print("does this also gets executed");
        return vals

If I replace the while loop with the if statement, it works right. I have tested with insertion pattern

t = Node()
t.insert(20)
t.insert(6)
t.insert(35)
vals = []
t.Inorder(vals)
print(vals)

Here is the whole class including the test patterns

class Node(object):
    
    def __init__(self,val=None):
        self.val = val
        self.left = None
        self.right = None
        #print("constuctor called")
        
    def insert(self,val):
        if not self.val:
            self.val = val #by virtue of constructor
            print("value inserted at root = ",val)
            return
        
        if val < self.val:
            if self.left:
                #print("self.left.val = ",self.left.val)
                self.left.insert(val)
                return
            self.left = Node(val)
            print("value inserted on left = ",val)
            return
        else:
            if self.right:
                #print("exists self.right.val = ",self.right.val)
                self.right.insert(val)
                return
            self.right = Node(val)
            print("value inserted on right = ",val)
            return



    def Inorder(self, vals):
        while(self.left != None):
            print("Going left value seen = ",self.left.val)
            self.left.Inorder(vals)
        # if self.val is not None:
        vals.append(self.val)
        print("vals=",vals)
        if self.right is not None:
            print("Going right value seen = ",self.right.val)
            self.right.Inorder(vals)
        #print("does this also gets executed");
        return vals
        

  
            
   
t = Node()
t.insert(20)
t.insert(6)
t.insert(35)
# t.insert(3)
# t.insert(8)
# t.insert(27)
# t.insert(55)
print(t.val)
vals = []
t.Inorder(vals)
print(vals)

CodePudding user response：

You don't have infinite recursion, but an infinite loop. The while is testing self.left which is not being changed in the loop... so if self.left != None is true once, it will always be true.

It should be an if instead of a while. The recursion will take care of the actual walking down the tree.