181

Can someone please help me understand the following Morris inorder tree traversal algorithm without using stacks or recursion ? I was trying to understand how it works, but its just escaping me.

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

I understand the tree is modified in a way that the current node, is made the right child of the max node in right subtree and use this property for inorder traversal. But beyond that, I'm lost.

EDIT: Found this accompanying c++ code. I was having a hard time to understand how the tree is restored after it is modified. The magic lies in else clause, which is hit once the right leaf is modified. See code for details:

/* Function to traverse binary tree without recursion and
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;

  if(root == NULL)
     return; 

  current = root;
  while(current != NULL)
  {
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;
    }
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;

      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }

     // MAGIC OF RESTORING the Tree happens here: 
      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
      else
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}
6
  • 6
    I thought it might be useful to indicate the source of the pseudo-code + code (presumably). May 30, 2014 at 22:42
  • 1
    source : geeksforgeeks.org/… Nov 4, 2016 at 6:07
  • in the above code, following line is not required: pre->right = NULL; Dec 9, 2019 at 6:41
  • 1
    I think the pseudocode has an important error of omission. In step "a" of "Else" it says to mark predecessor of current and move left. This should say something like "if we bump into current while finding its own predecessor, unthread (optional, if you don't want to leave the tree threaded) and move right". I think that this is what @Talonj means by "dual-condition of the loop" in their excellent answer. The lesson here is that the code outranks the description.
    – bronzenose
    Nov 6, 2020 at 21:23
  • @bronzenose you are understating the importance of that part of the algorithm. Not only will this algorithm not terminate if you do not sever the connection in this way, this step is really the most brilliant part of the whole process! Trying to come up with alternate methods run into this same issue of destroying the tree and not being able to repair it. Feb 18, 2021 at 18:26

8 Answers 8

203

If I am reading the algorithm right, this should be an example of how it works:

     X
   /   \
  Y     Z
 / \   / \
A   B C   D

First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X's left subtree -- the immediate predecessor to X in an inorder traversal. So X is made the right child of B, then current is set to Y. The tree now looks like this:

    Y
   / \
  A   B
       \
        X
       / \
     (Y)  Z
         / \
        C   D

(Y) above refers to Y and all of its children, which are omitted for recursion issues. The important part is listed anyway. Now that the tree has a link back to X, the traversal continues...

 A
  \
   Y
  / \
(A)  B
      \
       X
      / \
    (Y)  Z
        / \
       C   D

Then A is outputted, because it has no left child, and current is returned to Y, which was made A's right child in the previous iteration. On the next iteration, Y has both children. However, the dual-condition of the loop makes it stop when it reaches itself, which is an indication that it's left subtree has already been traversed. So, it prints itself, and continues with its right subtree, which is B.

B prints itself, and then current becomes X, which goes through the same checking process as Y did, also realizing that its left subtree has been traversed, continuing with the Z. The rest of the tree follows the same pattern.

No recursion is necessary, because instead of relying on backtracking through a stack, a link back to the root of the (sub)tree is moved to the point at which it would be accessed in a recursive inorder tree traversal algorithm anyway -- after its left subtree has finished.

6
  • 4
    Thanks for the explanation. The left child is not severed, instead the tree is restored later on by severing the new right child that is added to the rightmost leaf for the purpose of traversal. See my updated post with the code. Mar 31, 2011 at 22:26
  • 1
    Nice sketch, but I still don't understand the while loop condition. Why is checking for pre->right != current necessary?
    – No_name
    Mar 12, 2013 at 1:18
  • 7
    I don't see why this works. After you print A, then Y becomes the root, and you still have A as the left child. Thus, we are in the same situation as before. And we repeat A. In fact, it looks like an infinite loop.
    – user678392
    Oct 21, 2013 at 21:51
  • Doesn't this sever the connection between Y and B? When X is set as current and Y is set as pre, then it's going to look down the right subtree of pre till it find current (X), and then it sets pre=>right as NULL, which would be B right? In accordance with the code posted above
    – Achint
    Mar 1, 2014 at 8:32
  • Wouldn't you still need to maintain a list of nodes that have been traversed, I wonder. @Talonj
    – 10101010
    Jul 9, 2021 at 18:13
26

The recursive in-order traversal is : (in-order(left)->key->in-order(right)). (this is similar to DFS)

When we do the DFS, we need to know where to backtrack to (that's why we normally keep a stack).

As we go through a parent node to which we will need to backtrack to -> we find the node which we will need to backtrack from and update its link to the parent node.

When we backtrack? When we cannot go further. When we cannot go further? When no left child's present.

Where we backtrack to? Notice: to SUCCESSOR!

So, as we follow nodes along left-child path, set the predecessor at each step to point to the current node. This way, the predecessors will have links to successors (a link for backtracking).

We follow left while we can until we need to backtrack. When we need to backtrack, we print the current node and follow the right link to the successor.

If we have just backtracked -> we need to follow the right child (we are done with left child).

How to tell whether we have just backtracked? Get the predecessor of the current node and check if it has a right link (to this node). If it has - than we followed it. remove the link to restore the tree.

If there was no left link => we did not backtrack and should proceed following left children.

Here's my Java code (Sorry, it is not C++)

public static <T> List<T> traverse(Node<T> bstRoot) {
    Node<T> current = bstRoot;
    List<T> result = new ArrayList<>();
    Node<T> prev = null;
    while (current != null) {
        // 1. we backtracked here. follow the right link as we are done with left sub-tree (we do left, then right)
        if (weBacktrackedTo(current)) {
            assert prev != null;
            // 1.1 clean the backtracking link we created before
            prev.right = null;
            // 1.2 output this node's key (we backtrack from left -> we are finished with left sub-tree. we need to print this node and go to right sub-tree: inOrder(left)->key->inOrder(right)
            result.add(current.key);
            // 1.15 move to the right sub-tree (as we are done with left sub-tree).
            prev = current;
            current = current.right;
        }
        // 2. we are still tracking -> going deep in the left
        else {
            // 15. reached sink (the leftmost element in current subtree) and need to backtrack
            if (needToBacktrack(current)) {
                // 15.1 return the leftmost element as it's the current min
                result.add(current.key);
                // 15.2 backtrack:
                prev = current;
                current = current.right;
            }
            // 4. can go deeper -> go as deep as we can (this is like dfs!)
            else {
                // 4.1 set backtracking link for future use (this is one of parents)
                setBacktrackLinkTo(current);
                // 4.2 go deeper
                prev = current;
                current = current.left;
            }
        }
    }
    return result;
}

private static <T> void setBacktrackLinkTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return;
    predecessor.right = current;
}

private static boolean needToBacktrack(Node current) {
    return current.left == null;
}

private static <T> boolean weBacktrackedTo(Node<T> current) {
    Node<T> predecessor = getPredecessor(current);
    if (predecessor == null) return false;
    return predecessor.right == current;
}

private static <T> Node<T> getPredecessor(Node<T> current) {
    // predecessor of current is the rightmost element in left sub-tree
    Node<T> result = current.left;
    if (result == null) return null;
    while(result.right != null
            // this check is for the case when we have already found the predecessor and set the successor of it to point to current (through right link)
            && result.right != current) {
        result = result.right;
    }
    return result;
}
2
  • 6
    I like your answer a lot because it provides the high level reasoning towards coming up with this solution!
    – KFL
    Feb 9, 2018 at 20:11
  • 3
    Desperately need a diagram
    – NoName
    Jan 29, 2021 at 9:02
21

I've made an animation for the algorithm here: https://docs.google.com/presentation/d/11GWAeUN0ckP7yjHrQkIB0WT9ZUhDBSa-WR0VsPU38fg/edit?usp=sharing

Animation of Morris traversal algorithm

This should hopefully help to understand. The blue circle is the cursor and each slide is an iteration of the outer while loop.

Here's code for morris traversal (I copied and modified it from geeks for geeks):

def MorrisTraversal(root):
    # Set cursor to root of binary tree
    cursor = root
    while cursor is not None:
        if cursor.left is None:
            print(cursor.value)
            cursor = cursor.right
        else:
            # Find the inorder predecessor of cursor
            pre = cursor.left
            while True:
                if pre.right is None:
                    pre.right = cursor
                    cursor = cursor.left
                    break
                if pre.right is cursor:
                    pre.right = None
                    cursor = cursor.right
                    break
                pre = pre.right
#And now for some tests. Try "pip3 install binarytree" to get the needed package which will visually display random binary trees
import binarytree as b
for _ in range(10):
    print()
    print("Example #",_)
    tree=b.tree()
    print(tree)
    MorrisTraversal(tree)
3
  • 4
    Your animation is quite interesting. Please consider making it into an image which would be included into your post, as external links often die after some time.
    – laancelot
    Oct 1, 2019 at 20:47
  • 7
    The animation is helpful!
    – yyFred
    Jan 3, 2020 at 8:35
  • 1
    great spreadsheet and usage of the binarytree library. but the code isn't correct, it fails to print the root nodes. you need to add print(cursor.value) after pre.right = None line
    – satnam
    Jan 31, 2020 at 22:38
11

I found a very good pictorial explanation of Morris Traversal.

Morris Traversal

2
  • Link only answer will lose its value when the link is broken in future, please add the relevant context from the link into answer. Jan 15, 2020 at 19:03
  • Sure. I'll add it soon. Jan 15, 2020 at 19:05
3
public static void morrisInOrder(Node root) {
        Node cur = root;
        Node pre;
        while (cur!=null){
            if (cur.left==null){
                System.out.println(cur.value);      
                cur = cur.right; // move to next right node
            }
            else {  // has a left subtree
                pre = cur.left;
                while (pre.right!=null){  // find rightmost
                    pre = pre.right;
                }
                pre.right = cur;  // put cur after the pre node
                Node temp = cur;  // store cur node
                cur = cur.left;  // move cur to the top of the new tree
                temp.left = null;   // original cur left be null, avoid infinite loops
            }        
        }
    }

I think this code would be better to understand, just use a null to avoid infinite loops, don't have to use magic else. It can be easily modified to preorder.

3
  • 2
    The solution is very neat but there is one problem. According to Knuth the tree should not be modified in the end. By doing temp.left = null tree will be lost.
    – Ankur
    Jun 27, 2015 at 13:09
  • This method can be used in places like converting a binary tree into linked list.
    – cyber_raj
    Aug 9, 2016 at 19:03
  • Like what @Shan said, the algorithm should not alter the original tree. While your algorithm works for traversing it, it destroys the original tree. Therefore, this is actually different than the original algorithm and therefore misleading. Jan 4, 2017 at 19:26
2

I hope the pseudo-code below is more revealing:

node = root
while node != null
    if node.left == null
        visit the node
        node = node.right
    else
        let pred_node be the inorder predecessor of node
        if pred_node.right == null /* create threading in the binary tree */
            pred_node.right = node
            node = node.left
        else         /* remove threading from the binary tree */
            pred_node.right = null 
            visit the node
            node = node.right

Referring to the C++ code in the question, the inner while loop finds the in-order predecessor of the current node. In a standard binary tree, the right child of the predecessor must be null, while in the threaded version the right child must point to the current node. If the right child is null, it is set to the current node, effectively creating the threading, which is used as a returning point that would otherwise have to be on stored, usually on a stack. If the right child is not null, then the algorithm makes sure that the original tree is restored, and then continues traversal in the right subtree (in this case it is known that the left subtree was visited).

0

Python Solution Time Complexity : O(n) Space Complexity : O(1)

Excellent Morris Inorder Traversal Explanation

class Solution(object):
def inorderTraversal(self, current):
    soln = []
    while(current is not None):    #This Means we have reached Right Most Node i.e end of LDR traversal

        if(current.left is not None):  #If Left Exists traverse Left First
            pre = current.left   #Goal is to find the node which will be just before the current node i.e predecessor of current node, let's say current is D in LDR goal is to find L here
            while(pre.right is not None and pre.right != current ): #Find predecesor here
                pre = pre.right
            if(pre.right is None):  #In this case predecessor is found , now link this predecessor to current so that there is a path and current is not lost
                pre.right = current
                current = current.left
            else:                   #This means we have traverse all nodes left to current so in LDR traversal of L is done
                soln.append(current.val) 
                pre.right = None       #Remove the link tree restored to original here 
                current = current.right
        else:               #In LDR  LD traversal is done move to R  
            soln.append(current.val)
            current = current.right

    return soln
1
  • 1
    I'm sorry, but this is unfortunately not a direct answer to the question. The OP asked for an explanation for how it works, not an implementation, possibly because they want to implement the algorithm themselves. Your comments are good for someone who already understands the algorithm, but OP doesn't yet. Also, as a policy, answers should be self-contained instead of merely linking to some outside resource, because the link could change or break over time. It's ok to include links, but if you do, you should also include at least the gist of what the link is providing. Apr 6, 2020 at 17:32
0

PFB Explanation of Morris In-order Traversal.

  public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class MorrisTraversal
    {
        public static IList<int> InOrderTraversal(TreeNode root)
        {
            IList<int> list = new List<int>();
            var current = root;
            while (current != null)
            {
                //When there exist no left subtree
                if (current.left == null)
                {
                    list.Add(current.val);
                    current = current.right;
                }
                else
                {
                    //Get Inorder Predecessor
                    //In Order Predecessor is the node which will be printed before
                    //the current node when the tree is printed in inorder.
                    //Example:- {1,2,3,4} is inorder of the tree so inorder predecessor of 2 is node having value 1
                    var inOrderPredecessorNode = GetInorderPredecessor(current);
                    //If the current Predeccessor right is the current node it means is already printed.
                    //So we need to break the thread.
                    if (inOrderPredecessorNode.right != current)
                    {
                        inOrderPredecessorNode.right = null;
                        list.Add(current.val);
                        current = current.right;
                    }//Creating thread of the current node with in order predecessor.
                    else
                    {
                        inOrderPredecessorNode.right = current;
                        current = current.left;
                    }
                }
            }

            return list;
        }

        private static TreeNode GetInorderPredecessor(TreeNode current)
        {
            var inOrderPredecessorNode = current.left;
            //Finding Extreme right node of the left subtree
            //inOrderPredecessorNode.right != current check is added to detect loop
            while (inOrderPredecessorNode.right != null && inOrderPredecessorNode.right != current)
            {
                inOrderPredecessorNode = inOrderPredecessorNode.right;
            }

            return inOrderPredecessorNode;
        }
    }

Not the answer you're looking for? Browse other questions tagged or ask your own question.