[LeetCode] Validate Binary Search Tree

 

 

Problem

 

 

---

 

Recursive Solution

 

Use inorder traversal to go through the BST. If the value of current node is smaller than or equal to the value of previous node, the BST is not valid.

When using recursion, verify the left side of the tree first. After reaching the very left node, move up to the root while checking the right nodes of each node on the way. Then check the right side of the tree.

 

I tried making a prev variable and passing it between recursions, but prev gets back to being null when the recursive function returns because it is a local variable. Lists can be modified via pass-by-reference, so use a list to store previous value. https://stackoverflow.com/questions/986006/how-do-i-pass-a-variable-by-reference

 

How do I pass a variable by reference?

 

 

 

 

Time Complexity

O(N) (worst case, when the tree is valid or invalid node was the rightmost one)

 

 

Space Complexity

O(N) (recursion stack)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        return self.isInOrder(root, [])
        
    def isInOrder(self, node, prev):
        if not node:
            return True
        if not self.isInOrder(node.left, prev):
            return False
        if not prev:
            prev.append(node.val)
        elif node.val <= prev[0]:
            return False
        prev[0] = node.val
        
        return self.isInOrder(node.right, prev)

 

 

 

Iterative Solution

 

 

Time Complexity

O(N) (worst case, when the tree is valid or invalid node was the rightmost one)

 

 

Space Complexity

O(N) (stack)

 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        stack = []
        prev = None
        
        while stack or root:
            # go to the leftmost node
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if prev is not None:
                if root.val <= prev:
                    return False
            prev = root.val
            root = root.right
        return True