Morris inorder Traversal

Question

learning morris inorder traversal from here: http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ and Explain Morris inorder tree traversal without using stacks or recursion

I am confused. 3 questions are in the comments. Help will be welcomed. Thanks

    while (current != null) {
        if (current.left == null) {
            visit(current);
            current = current.right;
        } else {
            pre = current.left;
            while (pre.right != null && pre.right != current) {
                pre = pre.right;
            } // Q1: why "pre.right != current"?
              // pre is initialized as current.left and will go right until null, 
              // why compare pre.right with current?

            if (pre.right == null) {
                pre.right = current;
                current = current.left;
            } else { // Q2: In which case, pre.right is not null and program gets here?
                pre.right = null;// Q3: why set pre.right to null?
                visit(current);
                current = current.right;
            }   

        } 

    }

score 1 · Accepted Answer · answered Apr 27 '16 at 21:02

OK, if I understand correctly, this traversal essentially restructures the tree so that the left most node is at the root of the tree. So something that starts off like this:

     D
   /   \
  B     F
 / \   / \
A   C E   G

Will look like this:

A
 \
  B
 / \
A'  C
     \
      D
     / \
    B'  F
       / \
      E   G

Where A' is A and all its subtrees.

After visiting, it will reconstruct the tree back.

To answer your questions:

Q1

Before the reconstruction, pre.right != current will never be a loop-ending condition, i.e. it will never be true. However, after the reconstruction, imagine if current held B. pre would be set to A', which is the same as A. pre.right == A'.right == A.right == current. Since this means that the A' node was already visited, it breaks the loop and reconstructs it, which leads to your next question.

Q2

Again, this case never happens prior to the reconstruction of the tree, but after the reconstruction, this is the "what to do" when you reach a node that's already been visited. Which again leads to your next question.

Q3

pre.right is set to null because it means prior to the reconstruction, the pre.right was originally null. Looking at the case post-reconstruction, node B, pre is set to A, which was a leaf node, and had no right child. Thus fixing it back:

  B
 / \
A   C
     \
      D
     / \
    B'  F
       / \
      E   G

As you can see, A' turned into just A since it's right child is no longer B but null.

Essentially, to help you understand it a bit better:

Morris traversal reconstructs the tree to have it's root as it's left most node(Also note that it now has cyclic paths)
Once it's been reconstructed, it will then visit, then fix the reconstruction back to the original form.

Morris inorder Traversal

1 Answers1