Your code would work properly if the tree would remain balanced after deletion. The main cause of your problem is explained below:
Here is the left subtree after you remove the node with value 10.
14
/ \
3 12
/ \ \
1 4 13
If we want to find the node with value 12, according to your code the 12 is compared with 14. If the 12 < 14, the search is done in the left subtree, otherwise in the right one. Obviously, the search return false because the node 12 (as well as the node 13) is located in the right subtree.
To solve the problem you should keep the tree balanced.