TreeNode insert(TreeNode x, int val) {
        if (x == null) return new TreeNode(val);
        if (x.val < val)
            x.right = insert(x.right, val);
        else if (x.val > val)
            x.left = insert(x.left, val);
        return x;
    }
Solution 1:
solution one building valid bst from preorder traversal of input tree and check if they are the same
src/problems/medium/ValidateBinarySearchTree.java