Posted on by Kalkicode
Code Binary Tree

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

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.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment