#include <iostream>
#include <stdio.h>
#include <stdlib.h>

struct BinaryTreeNode{
    char value;
    struct BinaryTreeNode *lchild, *rchild;
};

// 输入值依次是：a、b、#、#、c、#、#
struct BinaryTreeNode *creatBiTree() {
    struct BinaryTreeNode *node;
    char data;
    std::cin>>data;
    if (data == '#') {
        node = NULL;
    } else {
        node = (struct BinaryTreeNode *)malloc(sizeof(struct BinaryTreeNode *));
        node->value = data;
        node->lchild = creatBiTree();
        node->rchild = creatBiTree();
    };
    return node;
}

struct BinaryTreeNode * searchNode(struct BinaryTreeNode *node) {
    struct BinaryTreeNode * endNode = NULL;
    if (node == NULL) {
        return NULL;
    }
    if (node->value == 'c') {
        endNode = node;
    } else {
        if (endNode == NULL) {
            endNode =  searchNode(node->lchild);
        }
        if (endNode == NULL) {
            endNode = searchNode(node->rchild);
        }
    }
    return endNode;
}


int main(int argc, const char * argv[]) {
    struct BinaryTreeNode *rootNode = creatBiTree();
    struct BinaryTreeNode *endNode = searchNode(rootNode);
    
    printf("%d", endNode->value);
    return 0;
}