Validate Binary Search Tree | Leetcode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

---

Solution: Drill down the tree into the left and right children. For each drill down, add a boundary condition, either left or right bound. For the left child, add the right bound of the parent node's value. For the right child, add the left bound of the parent node's value.

Algorithm 1: Recursive (Simpler, but bounded by stack memory)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode node, Integer leftBound, Integer rightBound) {
        if (node == null) return true;
        if (leftBound != null && node.val <= leftBound) return false;
        if (rightBound != null && node.val >= rightBound) return false;
        return isValidBST(node.left, leftBound, node.val)
                && isValidBST(node.right, node.val, rightBound);
    }
}

Algorithm 2: Iterative (More verbose, but not bounded by stack memory)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private static class BoundedNode {
        private TreeNode node;
        private Integer leftBound;
        private Integer rightBound;
        
        private BoundedNode(TreeNode node, Integer leftBound, Integer rightBound) {
            this.node = node;
            this.leftBound = leftBound;
            this.rightBound = rightBound;
        }
    }
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        
        // Using stack or queue does not matter.
        Stack<BoundedNode> stack = new Stack<>();
        stack.push(new BoundedNode(root, null, null));
        
        do {
            BoundedNode b = stack.pop();
            if (b.leftBound != null && b.node.val <= b.leftBound) return false;
            if (b.rightBound != null && b.node.val >= b.rightBound) return false;
            if (b.node.left != null) {
                stack.push(new BoundedNode(b.node.left, b.leftBound, b.node.val));
            }
            if (b.node.right != null) {
                stack.push(new BoundedNode(b.node.right, b.node.val, b.rightBound));
            }
        } while (!stack.isEmpty());
        
        return true;
    }
}