Bei Binärbäumen möchte ich den nächsten Knoten in fortlaufender Reihenfolge hinzufügen, mein Algorithmus funktioniert jedoch nicht ganz

Question

Zum Beispiel, wenn ich

  A
 / \
 B  C
/  
D 

Ich würde mir wünschen, dass der nächste Zusatz lautet:

  A
 / \
 B  C
/ \ 
D  E

Aber ich habe große Schwierigkeiten zu erkennen, wo die nächste Stelle für die Eingabe des Gegenstands sein wird. Ich habe den folgenden Code:

    public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
        if (tree.getLeft() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachLeft(newTree);
        }
        else if (tree.getRight() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachRight(newTree);
        }
        // Both are non-null
        else {
            if (tree.getLeft().getLeft() == null || tree.getLeft().getRight() == null) {
                tree.attachLeft(addToTree(tree.getLeft(), name));
            }
            else if (tree.getRight().getLeft() == null || tree.getRight().getRight() == null) {
                tree.attachRight(addToTree(tree.getRight(), name));
            }
        }

        return tree;
    }

Aber es funktioniert nur für einen Baum mit drei Ebenen. Wenn ich versuche, die vierte Ebene hinzuzufügen, wird nichts mehr hinzugefügt.

Wie kann ich es so implementieren, dass es herausfindet, wo das nächste Element null ist, und es dann dort hinzufügen?

Ich dachte auch daran, eine checkNullity() Methode, wobei ich einen Baum nehmen würde, und überprüfen Sie, ob seine Kinder null waren, aber ich war auch mit Schwierigkeiten herauszufinden, wie die Kinder der Kinder zu erhalten. Ich wollte herausfinden, wo es null war und dann fügen Sie es dort.

Kann jemand etwas dazu sagen?