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

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);
        }
}

Source :Wiki Tree Traversal

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

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