#include<cstdio>
    #include<iomanip>
    #include<cassert>
    #include<string>
    #include<cmath>
    #include<iostream>
    #include<sstream>
    #include<stdio.h>
    #include<stdlib.h>
     using namespace std;

  const int N = 20;
  const int base = 64;
  const int alphsize = 26;

  struct bstnode;

  typedef bstnode*bst;

  struct bstnode
   {
    char kye;  
    bst lft = NULL;
    bst rght = NULL;
   };

  void sketsh(bst root,int dpth)
   {
    if(root)
     {
      sketsh(root->rght,dpth+1);
      for(int d = 0; d < dpth; d++) cout << " ";
      cout << root->kye << endl;
      sketsh(root->lft,dpth+1);
     }
   }

  bst mainroot;

  void insrt(bst&root,char newkye)
   {
    if(root==NULL)
     {
      root = new bstnode();
      root->kye = newkye;
     }
    else if(newkye < root->kye) insrt(root->lft,newkye);
    else insrt(root->rght,newkye);  // insrts duplicates to the rght
   }

  void preorder(bst root)
   {
    if(root)
     {
      cout << root->kye;
      preorder(root->lft);
      preorder(root->rght);
     }
   }

  void inorder(bst root)
   {
    if(root)
     {
      inorder(root->lft);
      cout << root->kye;
      inorder(root->rght);
     }
   }

  void postorder(bst root)
   {
    if(root)
     {
      postorder(root->lft);
      postorder(root->rght);
      cout << root->kye;
     }
   }

  int kount(bst root)
   {
    if(root == NULL) return 0;
    else return 1+kount(root->lft)+kount(root->rght);
   }

  int hite(bst root)
   {
    if(root == NULL) return -1;
    else return 1 + max(hite(root->lft),hite(root->rght));
   }

  bst lftmost(bst root)
   {
    assert(root);
    if(root->lft)
     return lftmost(root->lft);
    else return root;
   }

  void dlete(bst&root,bst&runr) // runner
    // moves inorder successor of root to root
   {
    assert(runr);
    if(runr->lft)
     dlete(root,runr->lft);
    else
     {
      bst tmp = runr;
      runr = runr->rght;
      tmp->lft = root->lft;
      tmp->rght = root->rght;
      root = tmp;
     }
   }

  void dlete(bst&root)
   {
    if(root->lft)
     if(root->rght)
      if(root->rght->lft)
       dlete(root,root->rght->lft);
      else
       {
        root->rght->lft = root->lft;
        root = root->rght;
       }
     else root = root->lft;
    else root = root->rght;
   }

  void dlete(bst&root,char dlt) // dlt = key of datum to be deleted
   {
    if(root) // if root is null write not found
     if(root->kye == dlt)
      dlete(root);
     else if(dlt < root->kye)
      dlete(root->lft,dlt);
     else
      dlete(root->rght,dlt);
    else cout << " Not found ";
   }

  bool iskey(bst root,char fnd) // fnd = key to find
   {
    if(root)
     if(root->kye == fnd) return true;
      else if(fnd < root->kye) return iskey(root->lft,fnd);
       else return iskey(root->rght,fnd);
    else return false;
   }

  bst findbst(bst root,char fnd) // fnd = key to find
   {
    if(root)
     if(root->kye == fnd) return root;
      else if(fnd < root->kye) return findbst(root->lft,fnd);
       else return findbst(root->rght,fnd);
    else return NULL;
   }

  void findall(bst root)
   {
    for(int i = 1; i <= alphsize; i++)
     {
      char fnd = char(base+i);
      cout << fnd;
      if(iskey(root,fnd)) cout << " Found" << endl;
      else cout << " Not found" << endl;
     }
   }

  void dsplay(bst root)
   {
    cout << "preorder:  ";
    preorder(root);
    cout << endl;
    cout << "inorder:   ";
    inorder(root);
    cout << endl;
    cout << "postorder: ";
    postorder(root);
    cout << endl;
    cout << "The tree has " << kount(root) << " nodes and height "
         << hite(root) << endl;
    sketsh(root,0);
   }

  int main()
   {
    char k;
    for(int i = 0; i < N; i++)
     {
      cin >> k; 
      insrt(mainroot,k);
     }
    dsplay(mainroot);
    cout << "Delete U:  ";
    dlete(mainroot,'U');
    cout << endl;
    dsplay(mainroot);
    cout << "Delete B:  ";
    dlete(mainroot,'B');
    cout << endl;
    dsplay(mainroot);
    findall(mainroot);
    return 1;
   }