Временная сложность обхода дерева двоичных деревьев InOrder O (n)?

Question

public void iterativePreorder(Node root) {
        Stack nodes = new Stack();
        nodes.push(root);

        Node currentNode;

        while (!nodes.isEmpty()) {
                currentNode = nodes.pop();
                Node right = currentNode.right();
                if (right != null) {
                        nodes.push(right);
                }
                Node left = currentNode.left();
                if (left != null) {
                        nodes.push(left);      
                }
                System.out.println("Node data: "+currentNode.data);
        }
}

Источник: Wiki Tree Traversal

Будет ли сложность времени O (n)?И будет ли сложность времени такой же, если она была сделана с использованием рекурсии?

Новый вопрос: Если бы мне пришлось использовать приведенный выше код, чтобы найти определенный узел из TreeA, чтобы создать другое дерево TreeB, которое будет иметьстолько же узлов, сколько TreeA, тогда сложность создания TreeB будет равна O (n ^ 2), поскольку это n узлов, и каждый узел будет использовать приведенный выше код O (n)?

Answer 1

Поскольку обход двоичного дерева (в отличие от поиска и большинства других операций с деревом) требует обработки всех узлов дерева, минимальная сложность любого алгоритма обходаO (n), т. Е. Линейный по количеству узлов в дереве.Это неизменный факт, который не изменится в общем случае, если кто-то не создаст квантовый компьютер или что-то в этом роде ...

Что касается рекурсии, то единственное отличие состоит в том, что рекурсивные вызовы методов создают стек неявным образом, нажимаявызовите фреймы в стек JVM, в то время как ваш пример кода создает стек явно.Я бы предпочел не спекулировать на какой-либо разнице в производительности между ними - вам следует профилировать и сравнивать обе альтернативы для каждого конкретного сценария использования.