//ABC00DE0G00F000
//abd00e00c00
#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
    char val;
    TreeNode *left;
    TreeNode *right;

};


TreeNode* Build()
{
    char c;
    cin>>c;
    if(c=='0') return NULL;

    //先序输入
    TreeNode *t=new TreeNode;
    t->val=c;
    t->left=Build();
    t->right=Build();

    return t;
}

void levelorder(TreeNode* root)//层序遍历
{
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* t=q.front();
        q.pop();
        cout<<t->val<<' ';
        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);

    }
}

int height(TreeNode* root)//递归求树高
{
    if(!root) return 0;
    else return max(height(root->left),height(root->right))+1;
}

int height2(TreeNode* root)//非递归求树高
{
    queue<TreeNode*> q;
    int height=0;
    q.push(root);
    while(q.size())
    {
        int n=q.size();
        while(n--)
        {
            TreeNode* t=q.front();
            q.pop();
            if(t->left)q.push(t->left);
            if(t->right)q.push(t->right);
        }
        height++;
    }
    return height;
}

bool isCompleteTree(TreeNode* root)//是否是完全二叉树
{
    queue<TreeNode*> q;
    q.push(root);
    bool leaf=false;//是否遇到叶子节点
    while(q.size())
    {
        TreeNode *t=q.front();
        q.pop();

        //若之前遇到叶子节点 且当前节点还有子节点返回false
        if(leaf&&(t->left||t->right))return false;
        //若遇到叶子节点
        if(!t->left&&!t->right) leaf=true;
        //若左子树为空右子树不为空
        if(!t->left&&t->right) return false;

        if(t->left)q.push(t->left);
        if(t->right)q.push(t->right);
    }
    return true;
}

int res=0;
void dfs(TreeNode* root) //判断每个结点是否有两个分支递归做法
{
    if(!root)return;
    if(root->left&&root->right)res++;
    dfs(root->left);
    dfs(root->right);
}

void swapLeftRight(TreeNode* root)//将树的左右子树进行交换 之后调用层序输出
{
    if(!root)return;
    swap(root->left,root->right);
    swapLeftRight(root->left);
    swapLeftRight(root->right);
}


int res1=0,k=3,i=0;
void dfs2(TreeNode* root)//求先序遍历序列第k个元素的值
{
    i++;
    if(i==k)res1=root->val;
    if(root->left)dfs2(root->left);
    if(root->right)dfs2(root->right);

}

void dfs3(TreeNode* root,char x)//删除结点以x为根的子树
{
    if(!root) return;
    if(root->val==x) root=NULL;
    else
    {
        cout<<root->val<<' ';
        dfs3(root->left,x);
        dfs3(root->right,x);

    }
}
int main()
{

    TreeNode* root=Build();
    char x;
    cin>>x;
    /*
    levelorder(root);
    puts(" ");

    cout<<height(root)<<' ';
    cout<<height2(root)<<' ';

    if(isCompleteTree(root)==true)
    cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    dfs(root);
    cout<<res<<endl;


    swapLeftRight(root);
    levelorder(root);

    dfs2(root);
    cout<<(char)res1<<endl;//注意结点为字母需要转成字符型输出

    dfs3(root,x);
    */

    return 0;
}