public interface Node {

Условие

public interface Node { Node left(); Node right(); String value(); }

/* A B. C

BAC

    A
B.      C

D. E

DBAEC */

public class TreeWalker {

public String walk(Node node) {

}

}

Ответ

По примерам нужен симметричный обход: левое поддерево, текущий узел, правое поддерево. Для пустого дерева возвращаем пустую строку; значения собираем в один StringBuilder.

public String walk(Node node) {
    StringBuilder result = new StringBuilder();
    appendInOrder(node, result);
    return result.toString();
}

private void appendInOrder(Node node, StringBuilder result) {
    if (node == null) return;
    appendInOrder(node.left(), result);
    result.append(node.value());
    appendInOrder(node.right(), result);
}

Предполагаются дерево без циклов и ненулевые value. Время O(n + S), где S — длина результата; стек O(h), где h — высота дерева. Для очень глубокой цепочки нужен итеративный обход с явным стеком, чтобы избежать StackOverflowError.