Morris Traversal

Using Threaded Tree for Inorder Traversal | O(n) Time | O(1) Space

The idea of Morris Traversal is based on Threaded Binary Tree.

Definition Threaded Tree

A binary tree is threaded by making all right child pointers that would normally be a null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be a null point to the inorder predecessor of the node.

Morris Traversal

Using Morris Traversal, we can traverse the tree without using stack and recursion.

The idea is a binary tree of all right child pointers that would normally be a null point to the inorder successor of the node (if it exists)

In this traversal, links are created as successors, and nodes are printed using these links. Finally, the changes are reverted back to restore the original tree.

Approach

When we are currently at a node, the following cases can arise:

• Case 1: When the current node has no left subtree. In this scenario, there is nothing to be traversed on the left side, so we simply print the value of the current node and move to the right of the current node.
• Case 2: When there is a left subtree and the right-most child(in order successor) of this left subtree is pointing to null. In this case, we need to set the right-most child to point to the current node, instead of NULL and move to the left of the current node.

• Case 3: When there is a left subtree and the right-most child(in order successor) of this left subtree is already pointing to the current node. In this case, we know that the left subtree is already visited so we need to print the value of the current node and move to the right of the current node.

Code

Morris Traversal Inorder

void morrisTraversalInorder(Node* root){
  Node* current = root;
  while(current){
    if(current->left == NULL){
      cout << current->data << "\n";
      current = current->right;
    }
    else{
      // Find inorder predecessor
      Node* pred = current->left;
      while (pred->right && pred->right != current)
        pred = pred->right;
      
      if (pred->right == NULL) {
         pred->right = current;
         current = current->left;
      }
      else{
        cout << current->data << "\n";
        pred->right = NULL;
        current = current->right;
      }
    }
  }
}

Morris Traversal Preorder

void morrisTraversalInorder(Node* root){
  Node* current = root;
  while(current){
    if(current->left == NULL){
      cout << current->data << "\n";
      current = current->right;
    }
    else{
      // Find inorder predecessor
      Node* pred = current->left;
      while (pred->right && pred->right != current)
        pred = pred->right;
      
      if (pred->right == NULL) {
         cout << current->data << "\n";
         pred->right = current;
         current = current->left;
      }
      else{
        pred->right = NULL;
        current = current->right;
      }
    }
  }
}

Solve this problem : https://leetcode.com/problems/flatten-binary-tree-to-linked-list/