Python inorder solution, no extra memory (commented and explained)


  • 0
    N

    The idea here is to iterate over the tree inorder. If the iteration is not in ascending order ,we should stop the check and return False. The check stops after we find the first element that breaks the ascending order(although his parent up until the root will still be checked, but not the rest of the nodes)

    class Solution(object):
        def __init__(self):
            self.prev = None
            self.ordered = True
        def isValidBST(self, root):
            self._inorder(root)
            return self.ordered
    
        def _inorder(self, node):
    
            # There's no need to check if we know that the _inorder traversal
            # is not in ascending order
            if node and self.ordered:
                self._inorder(node.left)
    
                # Instead of printing the value like in normal _inorder traversal,
                # we check that the value is bigger than it's previous one (None is
                # smaller than any value so wer'e good for the first check).
                if node.val <= self.prev:
                    self.ordered = False
    
                self.prev = node.val
    
                self._inorder(node.right)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.