Morris Traversal: Inorder Tree Traversal without recursion and without stack (Java)

Tags: , , ,

Tree traversal is often implemented using Stack or Recursion. In this case, the space complexity is O(h), where h is the height of the tree. We describe a method based on Morris Traversal for tree traversal using O(1) space. 

The basic idea of Morris Traversal is that: For current Node Cur, we use the right most leaf of its left child to record the location of Cur.

Suppose we start from root, after running 

preOfRoot's right child will point to root. Now we can traverse the left branch of the tree. As preOfRoot will be last node in the visited path of root’s left branch, we can use its right child go back to the root node. 

The Java code for morris in order traverse is:

The following excellent figure demonstrate how the leaf’s node is used to point to the current node. 

morris inorder traverse example


The following is the implement of morris in order traverse In Java. Please note that we also have the preorder traverse implementation. There is just only one difference.