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

  struct bstnode;

  const int N = 14;

  typedef bstnode*bst;

  struct bstnode
   {
    char kee;  
    bst left = NULL;
    bst right = NULL;
   };

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

  bst mainroot;

  void insert(bst&root,char newkee)
   {
    if(root==NULL)
     {
      root = new bstnode();
      root->kee = newkee;
     }
    else if(newkee < root->kee) insert(root->left,newkee);
    else insert(root->right,newkee);  // inserts duplicates to the right
   }

  void preorder(bst root)
   {
    if(root)
     {
      cout << root->kee;
      preorder(root->left);
      preorder(root->right);
     }
   }

  void inorder(bst root)
   {
    if(root)
     {
      inorder(root->left);
      cout << root->kee;
      inorder(root->right);
     }
   }

  void postorder(bst root)
   {
    if(root)
     {
      postorder(root->left);
      postorder(root->right);
      cout << root->kee;
     }
   }

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

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

  bst leftmost(bst root)
   {
    assert(root);
    if(root->left)
     return leftmost(root->left);
    else return root;
   }

  void dlete(bst&root,bst&runr)
    // moves inorder successor of root->kee to root
   {
    assert(runr);
    if(runr->left)
     dlete(root,runr->left);
    else
     {
      root->kee = runr->kee;
      runr = runr->right;
     }
   }

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

  void dlete(bst&root,char kill)
   {
    if(root) // if root is null write not found
     if(root->kee == kill)
      dlete(root);
     else if(kill < root->kee)
      dlete(root->left,kill);
     else
      dlete(root->right,kill);
    else cout << " Not found";
   }

  void display(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; 
      insert(mainroot,k);
     }
    display(mainroot);
    char yew = char(85);
    cout << "Delete " << yew << ":  ";
    dlete(mainroot,yew);
    cout << endl;
    display(mainroot);
    cout << "Delete " << yew << ":  ";
    dlete(mainroot,yew);
    cout << endl;
    return 1;
   }