#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <unordered_set>
#include <algorithm>

using namespace std;

/* ======================= 节点定义 ======================= */
struct TreeNode {
    string val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;

    TreeNode(const string& v)
        : val(v), left(nullptr), right(nullptr), parent(nullptr) {}
};

/* ======================= 建树（增强前序） =======================
   输入示例：
   A B D # # E # # C # #
*/
TreeNode* buildTree(queue<string>& tokens, TreeNode* parent = nullptr) {
    if (tokens.empty()) return nullptr;

    string cur = tokens.front();
    tokens.pop();

    if (cur == "#") return nullptr;

    TreeNode* node = new TreeNode(cur);
    node->parent = parent;
    node->left  = buildTree(tokens, node);
    node->right = buildTree(tokens, node);
    return node;
}

/* ======================= DFS（前序） ======================= */
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

/* ======================= BFS（层序） ======================= */
void bfs(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        if (cur->left)  q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

/* ======================= 查找节点（DFS） ======================= */
TreeNode* findNode(TreeNode* root, const string& target) {
    if (!root) return nullptr;
    if (root->val == target) return root;

    TreeNode* leftRes = findNode(root->left, target);
    if (leftRes) return leftRes;

    return findNode(root->right, target);
}

/* ======================= 树高度 =======================
   空树高度 = -1
   单节点高度 = 0
*/
int height(TreeNode* root) {
    if (!root) return -1;
    return max(height(root->left), height(root->right)) + 1;
}

/* ======================= 添加节点 ======================= */
bool addNode(TreeNode* root, const string& parentVal,
             const string& newVal, bool isLeft) {
    if (!root) return false;

    if (root->val == parentVal) {
        if (isLeft && !root->left) {
            root->left = new TreeNode(newVal);
            root->left->parent = root;
            return true;
        }
        if (!isLeft && !root->right) {
            root->right = new TreeNode(newVal);
            root->right->parent = root;
            return true;
        }
        return false;
    }

    return addNode(root->left, parentVal, newVal, isLeft) ||
           addNode(root->right, parentVal, newVal, isLeft);
}

/* ======================= 删除整棵子树 ======================= */
void deleteSubtree(TreeNode* node) {
    if (!node) return;

    deleteSubtree(node->left);
    deleteSubtree(node->right);

    if (node->parent) {
        if (node->parent->left == node)
            node->parent->left = nullptr;
        else if (node->parent->right == node)
            node->parent->right = nullptr;
    }
    delete node;
}

/* ======================= 删除单个节点 ======================= */
void deleteNode(TreeNode* node) {
    if (!node) return;

    // 叶子节点
    if (!node->left && !node->right) {
        if (node->parent) {
            if (node->parent->left == node)
                node->parent->left = nullptr;
            else
                node->parent->right = nullptr;
        }
        delete node;
        return;
    }

    // 只有一个孩子
    if (!node->left || !node->right) {
        TreeNode* child = node->left ? node->left : node->right;
        child->parent = node->parent;
        if (node->parent) {
            if (node->parent->left == node)
                node->parent->left = child;
            else
                node->parent->right = child;
        }
        delete node;
        return;
    }

    // 两个孩子：中序后继替换
    TreeNode* succ = node->right;
    while (succ->left) succ = succ->left;
    node->val = succ->val;
    deleteNode(succ);
}

/* ======================= LCA（父指针法） ======================= */
TreeNode* lca_parent(TreeNode* a, TreeNode* b) {
    unordered_set<TreeNode*> vis;
    while (a) {
        vis.insert(a);
        a = a->parent;
    }
    while (b) {
        if (vis.count(b)) return b;
        b = b->parent;
    }
    return nullptr;
}

/* ======================= 示例主函数 ======================= */
int main() {
    /*
      输入示例（第一行用于建树）：
      A B D # # E # # C # #
    */
    string line;
    getline(cin, line);

    stringstream ss(line);
    queue<string> tokens;
    string tok;
    while (ss >> tok) tokens.push(tok);

    TreeNode* root = buildTree(tokens);

    cout << "DFS (preorder): ";
    preorder(root);
    cout << "\n";

    cout << "BFS: ";
    bfs(root);
    cout << "\n";

    cout << "Tree height: " << height(root) << "\n";

    TreeNode* x = findNode(root, "D");
    TreeNode* y = findNode(root, "E");
    if (x && y) {
        TreeNode* lca = lca_parent(x, y);
        if (lca)
            cout << "LCA of D and E: " << lca->val << "\n";
    }

    deleteSubtree(root);
    return 0;
}