Morris traversal for Inorder

Morris Traversal is a method to traverse a binary tree without using the stack or recursion, and it does so with constant extra space. In this post, we will explore the Morris Traversal algorithm for inorder traversal of a binary tree and provide an explanation along with examples and code.

Problem Statement

The problem we are trying to solve is to traverse a binary tree in the inorder fashion using the Morris Traversal technique. We want to achieve this traversal without using additional space for stack or recursion.

Example

Consider the binary tree provided in the code:

      4
    /   \
   8     3
  / \   / \
 1   6 7   2
    /  
   9

The inorder traversal of this tree should result in: 1 8 9 6 4 7 3 2

Idea to Solve

The main idea behind Morris Traversal is to use threaded binary trees. In a threaded binary tree, the right pointers of some nodes are made to point to the inorder successor (the node that would be visited next in an inorder traversal). This threading allows us to navigate the tree without using extra space while maintaining the ability to backtrack to the parent nodes.

Algorithm

1. Initialize current as the root of the tree.
2. While current is not null:
   • If current has no left child:
     • Print the value of current.
     • Move current to its right child.
   • If current has a left child:
     • Find the rightmost node in the left subtree of current. This node will be the inorder predecessor of current.
     • If the right child of this predecessor is null, set it to current and move current to its left child.
     • If the right child is already current, it means we've visited the left subtree. Print the value of current, revert the right child of the predecessor back to null, and move current to its right child.
3. Repeat step 2 until current becomes null.

Pseudocode

1. Initialize current as root
2. while current is not null:
  if current.left is null:
     print current.data
     current = current.right
  else:
     find the rightmost node in current's left subtree (predecessor)
     if predecessor.right is null:
        predecessor.right = current
        current = current.left
     else:
        print current.data
        predecessor.right = null
        current = current.right

Code Solution

1) Morris inorder traversal in java 2) Morris inorder traversal in c++ 3) Morris inorder traversal in c 4) Morris inorder traversal in golang 5) Morris inorder traversal in c# 6) Morris inorder traversal in php 7) Morris inorder traversal in node js 8) Morris inorder traversal in python 9) Morris inorder traversal in ruby 10) Morris inorder traversal in scala 11) Morris inorder traversal in swift 12) Morris inorder traversal in kotlin 13) Morris inorder traversal in typescript 14) Morris inorder traversal in vb.net

Time Complexity

The Morris Traversal algorithm has a time complexity of O(n), where n is the number of nodes in the binary tree. This is because each edge is traversed at most twice - once when establishing the threaded connections and once when following those connections.