import java.util.*;
import java.lang.*;
import java.io.*;
class BST
{
class node
{
int data;
node left;
node right;
public node(int c)
{
data=c;
left=null;
right=null;
}
}
public BST()
{
root=null;
}
node root;
void insert1(int d)
{
if (root==null) {root=new node(d);return;}
node curr=root,parent=root;
while(curr!=null)
{
parent=curr;
if (d>curr.data) curr=curr.right;
else curr=curr.left;
}
if(d>parent.data) parent.right=new node(d);
else parent.left=new node(d);
}
void insert2(int d)
{
root=insertR(root,d);
}
node insertR(node r,int d)
{
if (r==null) return new node(d);
else if(d>r.data) r.right=insertR(r.right,d);
else r.left=insertR(r.left,d);
return r;
}
boolean search(int d)
{
node curr=root;
while(curr!=null)
{
if(d==curr.data) return true;
else if(d>curr.data) curr=curr.right;
else curr=curr.left;
}
return false;
}
void print()
{
inorder(root);
preorder(root);
postorder(root);
DFS();
BFS();
}
void inorder(node r)
{
if (r!=null)
{
inorder(r.left);
inorder(r.right);
}
}
void preorder(node r)
{
if (r!=null)
{
preorder(r.left);
preorder(r.right);
}
}
void postorder(node r)
{
if (r!=null)
{
postorder(r.left);
postorder(r.right);
}
}
void DFS()
{
Stack<node> S=new Stack<node>();
if(root==null) return;
S.push(root);
while(S.size()!=0)
{
node n=S.pop();
if(n.right!=null) S.push(n.right);
if(n.left!=null) S.push(n.left);
}
}
void BFS()
{
Queue<node> Q=new LinkedList<node>();
if(root==null) return;
Q.add(root);
while(Q.size()!=0)
{
node n=Q.remove();
if(n.right!=null) Q.add(n.right);
if(n.left!=null) Q.add(n.left);
}
}
void delete(int d)
{
root = deleteR(root, d);
}
node deleteR(node r, int d)
{
if (r == null) return null;
if (d < r.data)
r.left = deleteR(r.left, d);
else if (d > r.data)
r.right = deleteR(r.right, d);
else {
if (r.left == null)
return r.right;
else if (r.right == null)
return r.left;
r.data = min(r.right);
r.right = deleteR(r.right, r.data);
}
return r;
}
int min(node r)
{
int m = r.data;
while (r.left != null)
{
m = r.left.data;
r = r.left;
}
return m;
}
}
class Ideone
{
{
BST b=new BST();
b.insert1(4);
b.insert1(5);
b.insert2(3);
b.insert2(1);
b.insert2(2);
b.insert1(7);
b.insert1(6);
b.print();
b.delete(4);
b.print();
System.
out.
println(b.
search(3)); }
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBCU1QKewoJY2xhc3Mgbm9kZQoJewoJCWludCBkYXRhOwoJCW5vZGUgbGVmdDsKCQlub2RlIHJpZ2h0OwoJcHVibGljIG5vZGUoaW50IGMpCgl7CgkJZGF0YT1jOwoJCWxlZnQ9bnVsbDsKCQlyaWdodD1udWxsOwoJfQoJfQpwdWJsaWMgQlNUKCkKewoJcm9vdD1udWxsOwp9Cm5vZGUgcm9vdDsKdm9pZCBpbnNlcnQxKGludCBkKQp7CglpZiAocm9vdD09bnVsbCkge3Jvb3Q9bmV3IG5vZGUoZCk7cmV0dXJuO30KCW5vZGUgY3Vycj1yb290LHBhcmVudD1yb290OwoJd2hpbGUoY3VyciE9bnVsbCkKCXsKCQlwYXJlbnQ9Y3VycjsKCQlpZiAoZD5jdXJyLmRhdGEpIGN1cnI9Y3Vyci5yaWdodDsKCQllbHNlIGN1cnI9Y3Vyci5sZWZ0OwoJfQoJaWYoZD5wYXJlbnQuZGF0YSkgcGFyZW50LnJpZ2h0PW5ldyBub2RlKGQpOwoJZWxzZSBwYXJlbnQubGVmdD1uZXcgbm9kZShkKTsKfQp2b2lkIGluc2VydDIoaW50IGQpCnsKCXJvb3Q9aW5zZXJ0Uihyb290LGQpOwp9Cm5vZGUgaW5zZXJ0Uihub2RlIHIsaW50IGQpCnsKCWlmIChyPT1udWxsKSByZXR1cm4gbmV3IG5vZGUoZCk7CgllbHNlIGlmKGQ+ci5kYXRhKSByLnJpZ2h0PWluc2VydFIoci5yaWdodCxkKTsKCWVsc2Ugci5sZWZ0PWluc2VydFIoci5sZWZ0LGQpOwoJcmV0dXJuIHI7Cn0KYm9vbGVhbiBzZWFyY2goaW50IGQpCnsKCW5vZGUgY3Vycj1yb290OwoJd2hpbGUoY3VyciE9bnVsbCkKCXsKCQlpZihkPT1jdXJyLmRhdGEpIHJldHVybiB0cnVlOwoJCWVsc2UgaWYoZD5jdXJyLmRhdGEpIGN1cnI9Y3Vyci5yaWdodDsKCQllbHNlIGN1cnI9Y3Vyci5sZWZ0OwoJfQoJcmV0dXJuIGZhbHNlOwp9Cgp2b2lkIHByaW50KCkKewoJaW5vcmRlcihyb290KTsKCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJcHJlb3JkZXIocm9vdCk7CglTeXN0ZW0ub3V0LnByaW50bG4oKTsKCXBvc3RvcmRlcihyb290KTsKCVN5c3RlbS5vdXQucHJpbnRsbigpOwoJREZTKCk7CglTeXN0ZW0ub3V0LnByaW50bG4oKTsKCUJGUygpOwoJU3lzdGVtLm91dC5wcmludGxuKCk7CgkKfQp2b2lkIGlub3JkZXIobm9kZSByKQp7CglpZiAociE9bnVsbCkKCXsKCQlpbm9yZGVyKHIubGVmdCk7CgkJU3lzdGVtLm91dC5wcmludChyLmRhdGErIiAiKTsKCQlpbm9yZGVyKHIucmlnaHQpOwoJfQp9CnZvaWQgcHJlb3JkZXIobm9kZSByKQp7CglpZiAociE9bnVsbCkKCXsKCQlTeXN0ZW0ub3V0LnByaW50KHIuZGF0YSsiICIpOwoJCXByZW9yZGVyKHIubGVmdCk7CgkJcHJlb3JkZXIoci5yaWdodCk7Cgl9Cn0Kdm9pZCBwb3N0b3JkZXIobm9kZSByKQp7CglpZiAociE9bnVsbCkKCXsKCQlwb3N0b3JkZXIoci5sZWZ0KTsKCQlwb3N0b3JkZXIoci5yaWdodCk7CgkJU3lzdGVtLm91dC5wcmludChyLmRhdGErIiAiKTsKCX0KfQp2b2lkIERGUygpCnsKCVN0YWNrPG5vZGU+IFM9bmV3IFN0YWNrPG5vZGU+KCk7CglpZihyb290PT1udWxsKSByZXR1cm47CglTLnB1c2gocm9vdCk7Cgl3aGlsZShTLnNpemUoKSE9MCkKCXsKCQlub2RlIG49Uy5wb3AoKTsKCQlTeXN0ZW0ub3V0LnByaW50KG4uZGF0YSsiICIpOwoJCWlmKG4ucmlnaHQhPW51bGwpIFMucHVzaChuLnJpZ2h0KTsKCQlpZihuLmxlZnQhPW51bGwpIFMucHVzaChuLmxlZnQpOwoJfSAKfQp2b2lkIEJGUygpCnsKCVF1ZXVlPG5vZGU+IFE9bmV3IExpbmtlZExpc3Q8bm9kZT4oKTsKCWlmKHJvb3Q9PW51bGwpIHJldHVybjsKCVEuYWRkKHJvb3QpOwoJd2hpbGUoUS5zaXplKCkhPTApCgl7CgkJbm9kZSBuPVEucmVtb3ZlKCk7CgkJU3lzdGVtLm91dC5wcmludChuLmRhdGErIiAiKTsKCQlpZihuLnJpZ2h0IT1udWxsKSBRLmFkZChuLnJpZ2h0KTsKCQlpZihuLmxlZnQhPW51bGwpIFEuYWRkKG4ubGVmdCk7Cgl9IAp9Cgp2b2lkIGRlbGV0ZShpbnQgZCkgCnsgCglyb290ID0gZGVsZXRlUihyb290LCBkKTsgCn0KCm5vZGUgZGVsZXRlUihub2RlIHIsIGludCBkKQogICAgewogICAgICAgIGlmIChyID09IG51bGwpIHJldHVybiBudWxsOwoJCWlmIChkIDwgci5kYXRhKQogICAgICAgICAgICByLmxlZnQgPSBkZWxldGVSKHIubGVmdCwgZCk7CiAgICAgICAgZWxzZSBpZiAoZCA+IHIuZGF0YSkKICAgICAgICAgICAgci5yaWdodCA9IGRlbGV0ZVIoci5yaWdodCwgZCk7CiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIGlmIChyLmxlZnQgPT0gbnVsbCkKICAgICAgICAgICAgICAgIHJldHVybiByLnJpZ2h0OwogICAgICAgICAgICBlbHNlIGlmIChyLnJpZ2h0ID09IG51bGwpCiAgICAgICAgICAgICAgICByZXR1cm4gci5sZWZ0OwogCiAgICAgICAgICAgIHIuZGF0YSA9IG1pbihyLnJpZ2h0KTsKICAgICAgICAgICAgci5yaWdodCA9IGRlbGV0ZVIoci5yaWdodCwgci5kYXRhKTsKICAgIAkJIH0KIAogICAgICAgIHJldHVybiByOwogICAgfQogCiAgICBpbnQgbWluKG5vZGUgcikKICAgIHsKICAgICAgICBpbnQgbSA9IHIuZGF0YTsKICAgICAgICB3aGlsZSAoci5sZWZ0ICE9IG51bGwpCiAgICAgICAgewogICAgICAgICAgICBtID0gci5sZWZ0LmRhdGE7CiAgICAgICAgICAgIHIgPSByLmxlZnQ7CiAgICAgICAgfQogICAgICAgIHJldHVybiBtOwogICAgfQp9CmNsYXNzIElkZW9uZQp7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCUJTVCBiPW5ldyBCU1QoKTsKCWIuaW5zZXJ0MSg0KTsKCWIuaW5zZXJ0MSg1KTsKCWIuaW5zZXJ0MigzKTsKCWIuaW5zZXJ0MigxKTsKCWIuaW5zZXJ0MigyKTsKCWIuaW5zZXJ0MSg3KTsKCWIuaW5zZXJ0MSg2KTsKCWIucHJpbnQoKTsKCWIuZGVsZXRlKDQpOwoJYi5wcmludCgpOwoJU3lzdGVtLm91dC5wcmludGxuKGIuc2VhcmNoKDMpKTsKCX0KfQ==