Validate BST:

• pass value down from parent to child
• max left child = parent.val, min right child = parent.val
• eval current node isBST by checking: root.val in [low, high], low and high is restricted by parent
• divide and conquer

    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean helper(TreeNode root, long low, long high) {

        if (root == null) return true;

        if (root.val <= low || root.val >= high) return false;

        boolean left = helper(root.left, low, root.val);
        boolean right = helper(root.right, root.val, high);

        return left && right;
    }

• eval current node isBST by checking: root.val in [left.max, right.min] && left.isBST && right.isBST
• ResultType: isBST, min, max -- min -> the min in the subtree, max -> the max in the subtree
• divide and conquer

class ResultType {
    long max;
    long min;
    boolean isBST;

    public ResultType(long min, long max, boolean isBST) {
        this.min = min;
        this.max = max;
        this.isBST = isBST;
    }
} 

public class Solution {

    public boolean isValidBST(TreeNode root) {
        return validate(root).isBST;
    }

    private ResultType validate(TreeNode root) {

        if (root == null) return new ResultType(Long.MAX_VALUE, Long.MIN_VALUE, true);

        ResultType left = validate(root.left);
        ResultType right = validate(root.right);

        if (!left.isBST || !right.isBST) return new ResultType(0, 0, false);
        if (root.val <= left.max || root.val >= right.min) return new ResultType(0, 0, false);

        return new ResultType(Math.min(root.val, left.min), Math.max(root.val, right.max), true);
    }
}

• use inorder traversal, iterative, stack

BST iterator:

public class BSTIterator {
    //@param root: The root of binary tree.
    private Stack<TreeNode> stack = new Stack<>();
    private TreeNode root;
    public BSTIterator(TreeNode root) {
        // write your code here
        this.root = root;
    }

    //@return: True if there has next node, or false
    public boolean hasNext() {
        // write your code here
        return (root != null || !stack.isEmpty());
    }

    //@return: return next node
    public TreeNode next() {
        // write your code here
        while (root != null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        TreeNode curr = root;
        root = root.right;

        return curr;
    }
}

Search Range in BST:

• notice when node meet critier, still need to go down.
• so not: root.val < k1, root.val > k2

    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
        // write your code here
        ArrayList<Integer> rst = new ArrayList<>();
        helper(root, k1, k2, rst);
        return rst;
    }

    private void helper(TreeNode root, int k1, int k2, ArrayList<Integer> rst) {

        if (root == null) {
            return;
        }

        if (root.val > k1) {
            helper(root.left, k1, k2, rst);
        }

        if (root.val >= k1 && root.val <= k2) {
            rst.add(root.val);
        }

        if (root.val < k2) {
            helper(root.right, k1, k2, rst);
        }
    }

Insert Node in a BST:

    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) {
            return node;
        }

        if (node.val > root.val) {
            root.right = insertNode(root.right, node);
        } else {
            root.left = insertNode(root.left, node);
        }
        return root;
    }