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``````

## 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.

Categories
Relative Post