#include <iostream>
#include <string>

using namespace std;
//string input = "amd*fu***e**ckl**r***";


// The input is from the console

struct Node
{
    struct Node* lchild;
    char data;
    struct Node* rchild;
};

typedef Node* point;
point Root;
void Create_B_Tree(point& P) {
    char x;
    cin >> x;
    if (x == '*') P = NULL;
    else {
        P = new Node;
        P->data = x;
       // cout << "left of " << P->data << "=";
        Create_B_Tree(P->lchild);
      //  cout << "right of" << P->data << "=";
        Create_B_Tree(P->rchild);
    }
}



int height(struct Node* p)
{
    if (p)
    {
        return 1 + max(height(p->rchild), height(p->lchild));
    }
    return 0;
}

/* Print nodes at a given level */
void printGivenLevel(struct Node* p, int level)
{
    if (p == NULL)
        return;
    if (level == 1)
    {
        printf("%c ", p->data);
        if (p->lchild)
            cout << " left child of" << p->data << " is: " << p->lchild->data << endl;
        else
            cout << p->data << " doesnt have left child" << endl;

        if (p->rchild)
			 cout << " right child of" << p->data << " is: " << p ->rchild->data << endl;
        else
            cout << p->data << " doesnt have right child" << endl;

    }
    else if (level > 1)
    {
        printGivenLevel(p->lchild, level - 1);
        printGivenLevel(p->rchild, level - 1);
    }
}

void printLevelOrder(struct Node* p)
{
    int h = height(p);
    int i;
    for (i = 1; i <= h; i++)
    {
        printGivenLevel(p, i);
        printf("\n");
    }
}


/* Print nodes at a given level */
void printGivenLevel2(struct Node* p, int level)
{
    if (p == NULL)
        return;
    if (level == 1)
    {
        printf("%c ", p->data);

    }
    else if (level > 1)
    {
        printGivenLevel2(p->lchild, level - 1);
        printGivenLevel2(p->rchild, level - 1);
    }
}

void printLevelOrder2(struct Node* p)
{
    int h = height(p);
    int i;
    for (i = 1; i <= h; i++)
    {
        printGivenLevel2(p, i);
        printf("\n");
    }
}

int main()
{
    cout << "Enter the whole input" << endl;
    Root = NULL;
    Create_B_Tree(Root);
    cout << endl;
    cout << "===============" << endl;
    printLevelOrder(Root);
    cout << "===============" << endl;
    printLevelOrder2(Root);


}