[98. Validate Binary Search Tree] #leetcode

98_1015.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

// recursive 
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean dfs(TreeNode node, long left, long right) {
        if ( node == null ) return true;
        
        return left < node.val && right > node.val && dfs(node.left, left, node.val) && dfs(node.right, node.val, right);
    }
}

98_1015.py

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

# iterative
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # corner case
        if not root:
            return True
        
        # stack to store temporal nodes
        stack = []
        preNode = None
        
        # in order iterate tree
        while (root != None or stack):
            while (root != None):
                stack.append(root)
                root = root.left
            root = stack.pop()
            # current value less than pre node value, it is False
            if (preNode != None and root.val <= preNode.val):
                return False
            preNode = root
            root = root.right
        
        # if no False, then it is True
        return True