バイナリツリーO（n）のInOrder Treeトラバーサルの時間複雑度？

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

出典：ウィキツリートラバーサル

はO（n）があることを行って時間複雑ですか？再帰を使用して完了した場合、時間の複雑さは同じになるでしょうか？

新しい質問： 私はTreeA限りのノードを持つことになり、別のツリーTreeBを作成するTreeAから特定のノードを見つけるために、上記のコードを使用した場合、その後、TreeB作成の複雑さは（OだろうN^2）それはn個のノードであり、各ノードはO（n）である上記のコードを使用するだろうから？ （検索および他のほとんどのツリーの操作とは対照的に）バイナリツリーのトラバーサルが全てツリーノードが処理されることを必要とするので

Answer 1

、任意トラバースアルゴリズムの最小の複雑さは、O（N）すなわち、線形でありますwrtツリー内のノードの数これは、誰かが量子コンピュータや何かを構築しない限り、一般的なケースでは変化しない不変の事実です...

唯一の違いは、再帰的メソッド呼び出しは、コールフレームをプッシュすることによって暗黙的にスタックを構築するサンプルコードはスタックを明示的に構築しています。むしろ、2つのパフォーマンスの違いについては推測しません。具体的なユースケースのシナリオごとに両方の選択肢をプロファイルし、ベンチマークする必要があります。