I am trying to solve a leetcode problem and am facing an issue with my code. What i want is that prev store the value of the previous node but when i run the recursive code the value of prev always becomes None.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        prev = None
        if root:
            if not self.isValidBST(root.left):
                return False
            
            if  prev is not None and prev >= root.val:
                return False
            prev = root.val
            return self.isValidBST(root.right)

Can you please explain why this code is failing especially why the value of prev always becomes None in every recursion call

CodePudding user response：

The problem has two reasons:

• prev is a local name, and whatever happens to the prev in a recursive call, it doesn't affect the value of prev at the side of the caller, since that is a distinct name. Concretely, the condition if prev is not None will never be true; prev is still None.
• Even if somehow you would make prev a nonlocal name so that all recursive calls would access the same prev, these calls (except for the base case), all set previs back toNone. But this is undesired: you should maintain the previous value, except for the case where the top-level (first) call is made: only then should prevbe initialised toNone`.

You can solve this by defining prev as a global variable, or better, as an attribute of self. This way there will be one prev that the recursive process will work with.

Since you need to initialise this prev to None only once, but have recursive calls, you should separate the initial call from the recursive calls, and perform that initialisation only in the initial call. For that purpose you can separate the function into two functions: the main one will perform the initialisation and call the other, recursive one:

class Solution:
    def isValidBSTHelper(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        if not self.isValidBSTHelper(root.left):
            return False
        if self.prev is not None and self.prev >= root.val:
            return False
        self.prev = root.val
        return self.isValidBSTHelper(root.right)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.prev = None  # Attribute has larger scope
        return self.isValidBSTHelper(root)

You can also make the inorder traversal with a generator, which has the recursive part, and then loop over the values from that iterator and compare them:

class Solution:
    def inorder(self, root: Optional[TreeNode]):
        if root:
            yield from self.inorder(root.left)
            yield root.val
            yield from self.inorder(root.right)
    
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        values = self.inorder(root)
        prev = next(values, None) # get first value and advance
        for val in values:
            if prev >= val:
                return False
            prev = val
        return True

or you could launch two inorder iterations, with one step difference, and use zip in isValidBST (the inorder function remains the same):

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        previous = self.inorder(root)
        values = self.inorder(root)
        next(values, None) # move one iterator one step forward
        return all(a < b for a, b in zip(previous, values)) # all pairs must be in order

CodePudding user response：

Can you please explain why this code is failing especially why the value of prev always becomes None in every recursion call

The variable prev is local to each frame (recursion/function call). On each recursion pass, you initialize it to None. This results that for example the condition if prev is not None and prev >= root.val: is never reached in your code, because on each evaluation prev is always None.

I think this response might be valuable to you: What is the relation between stack frame and a scope?

And this (it is from python1 docs but still valid): https://understanding-recursion.readthedocs.io