1. Validate Binary Search Tree

travese solution, inorder traverse! but this solution can not handle duplicates case! assume no dup!

public class Solution {
    public boolean isValidBST(TreeNode root) {

        if(root == null) return true;

        Stack<TreeNode> st = new Stack<>();
        TreeNode pre = null, cur = root;

        while(cur != null || !st.isEmpty()){
            while(cur != null){
                st.push(cur);
                cur = cur.left;
            }

            cur = st.pop();
            if(pre == null)
                pre = cur;
            else if(pre.val >= cur.val)
                return false;
            else
                pre = cur;

            cur = cur.right;
        }

        return true;
    }
}

recursive solution, can handle dup!

public class Solution {
    public boolean isValidBST(TreeNode root) {

        if(root == null) return true;

        return isValidBST(root, null, null);
    }

    public boolean isValidBST(TreeNode root, Integer min, Integer max) {

        if(root == null) return true;
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

note! careful with BST's definition.

2 Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

6, 3, 4, 5, 2

public class Solution {

    TreeNode first = null;
    TreeNode second= null;
    TreeNode pre   = null;

    public void recoverTree(TreeNode root) {

        inOrder(root);

        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

    public void inOrder(TreeNode root) {

        if(root == null)
            return;

        inOrder(root.left);

        if(pre != null && first == null && pre.val >= root.val)
            first = pre;

        if(first != null && pre.val >= root.val)// not else if!!!
            second = root;

        pre = root;

        inOrder(root.right);
    }
}

3. Kth Smallest Element in a BST

public class Solution {

    int count = 0;
    int res   = -1;
    public int kthSmallest(TreeNode root, int k) {

        if(root == null) return res;

        count = k;
        inOrder(root);
        return res;
    }

    public void inOrder(TreeNode root) {

        if(root == null)
            return;
        inOrder(root.left);

        count--;
        if(count == 0){
            res = root.val;
            return;
        }
        inOrder(root.right);
    }
}