title: Performance of Morris Traversal vs recursive In-Order in a binary tree
body: <p>I am doing some preparations before going to interviews and i just learned about Morris Traversal.</p>
  
  <p>This is Morris Traversal code which i wrote in Java(its working):</p>
  
  <pre><code>protected void morrisTraversal(){
      BinaryNode pre = null;//BinaryNode is a class which represent a node in the tree
      BinaryNode current = this.root;//root is the root of the tree
      while(current != null){
          if(current.getLeftChild() == null){
              System.out.println(current.getNodeData().getId());//id is unique
              current = current.getRightChild();
          }//if
          else{
              pre = current.getLeftChild();
              while(pre.getRightChild() != null &amp;&amp; pre.getRightChild().getNodeData().getId() != current.getNodeData().getId())
                  pre = pre.getRightChild();
              if(pre.getRightChild() == null){
                  pre.setRightChild(current);
                  current = current.getLeftChild();
              }//if
              else{
                  System.out.println(current.getNodeData().getId());
                  current = current.getRightChild();
                  pre.setRightChild(null);
              }//else
          }//else
      }//while
  }//MorrisTraversal
  </code></pre>
  
  <p>And here is my code for the In-Order method:</p>
  
  <pre><code>protected void recInOrder() {
      if(this.root != null)
          recInOrderHelper(this.root);
      else
          System.out.println("The Tree Is Empty");;
  }//recInOrder
  
  
  private void recInOrderHelper(BinaryNode node)  {
      if(node != null){
          recInOrderHelper(node.getLeftChild());
          System.out.println(node.getNodeData().getId());
          recInOrderHelper(node.getRightChild());
      }
  }//recInOrderHelper
  </code></pre>
  
  <p>And what i did in my main is:
  I inserted to my binary tree 70,000,000 nodes and then i did the next little checking:</p>
  
  <pre><code>long start = System.currentTimeMillis();
  tree4.morrisTraversalInOrder();
  System.out.println("morris traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");
  
  start = System.currentTimeMillis();
  tree4.recInOrder();
  System.out.println("recursive in-order TOOK: " + (System.currentTimeMillis() - start) + " ms");
  </code></pre>
  
  <p>And the results surprised me!</p>
  
  <p>Those are the results:</p>
  
  <p>Morris Traversal TOOK:  637 ms</p>
  
  <p>Recursive In-Order TOOK: 367 ms</p>
  
  <p><strong>NOTICE - when i did this test i commented all the System.out.println(...) from morrisTraversal() and from recInOrderHelper() methods.</strong></p>
  
  <p>Those results surprised me because i thought that Morris Traversal will be faster because its iterative(doesn't open stack frames etc) and In-Order is recursive(open approximately 70,000,000 stack frames for each recursive call)</p>
  
  <p>I know that both of them are O(n),
  So obviously i am wrong about some things, but which? what am i missing? why Morris Traversal is much slower than recursive In-Order?</p>
  
  <p><strong>EDIT</strong> - I also did the next testing:
  instead of inserting 70,000,000 nodes to the tree I inserted 100,000 nodes
  And I did ran the next code:</p>
  
  <pre><code>//running the two algorithms one time before doing the actual test(but in the same execution)
  tree4.recInOrder();
  tree4.morrisTraversalInOrder();
  
  //starting the actual test
  long start = System.currentTimeMillis();
  for(i = 0; i &lt; 100000; i++){
      tree4.recInOrder(); 
  }
  System.out.println("Recursive In-Order TOOK: " + (System.currentTimeMillis() - start) + " ms");
  
  start = System.currentTimeMillis();
  for(i = 0; i &lt; 100000; i++){
      tree4.morrisTraversalInOrder(); 
  }
  System.out.println("Morris Traversal TOOK: " + (System.currentTimeMillis() - start) + " ms");
  </code></pre>
  
  <p>And the results are:</p>
  
  <p>Recursive In-Order TOOK: 214434 ms</p>
  
  <p>Morris Traversal TOOK: 502786 ms</p>
  
  <p>And as you can see Morris Traversal is still very slow compared to recursive In-Order.
  So I did another testing and only inserted 1,000 nodes and ran each code only 10,000 times
  and the result are:</p>
  
  <p>Recursive In-Order TOOK: 44 ms</p>
  
  <p>Morris Traversal TOOK: 97 ms</p>
  
  <p>I still don't get it? why Morris Traversal is slower?</p>