If interviewer does not allow us to alter the values of nodes, we would need to manipulate the nodes by reference. Here's the solution in this case.

```
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
TreeNode pRoot = new TreeNode(0);
pRoot.left = root;
TreeNode p = pRoot, cur = root;
while (cur != null && cur.val != key) {
p = cur;
if (key < cur.val) {
cur = cur.left;
} else {
cur = cur.right;
}
}
if (cur == null) return root;
delete(cur, p);
return pRoot.left;
}
private TreeNode delete(TreeNode node, TreeNode p) {
if (node == null) return null;
boolean isLeft = p.left == node;
if (node.left == null) {
if (isLeft) p.left = node.right;
else p.right = node.right;
return node.right;
}
if (node.right == null) {
if (isLeft) p.left = node.left;
else p.right = node.left;
return node.left;
}
TreeNode left = node.left, right = node.right;
TreeNode p1 = node, left1 = left;
while (left1.right != null) {
p1 = left1;
left1 = left1.right;
}
TreeNode newLeft = delete(left1, p1);
if (left1 == left) left = newLeft;
left1.left = left;
left1.right = right;
if (isLeft) p.left = left1;
else p.right = left1;
return left1;
}
```