Posted on by Kalkicode
Code Binary Tree

# Morris traversal for Preorder

Morris Traversal is a special method for traversing binary trees without using recursion or an explicit stack. It allows us to perform both in-order and pre-order traversals of a binary tree using only constant space while maintaining the original structure of the tree. The algorithm was introduced by J. H. Morris in 1979.

## Problem Statement

Given a binary tree, we want to perform a pre-order traversal using the Morris Traversal technique. The goal is to print the values of the nodes in pre-order sequence.

## Description

The Morris Traversal algorithm is based on the idea of threaded binary trees, where we temporarily modify the structure of the tree to create threads connecting some nodes. These threads help us traverse the tree without using a stack or recursion.

Let's understand the algorithm with an example:

Consider the binary tree:

``````
4
/   \
8     10
/ \   /  \
1   6 7   -3
/
9``````

## Idea to Solve the Problem

2. Initialize the current node as the root.
3. While the current node is not null: a. If the current node doesn't have a left child, print its value and move to the right child. b. If the current node has a left child: i. Find the rightmost node in the left subtree of the current node. ii. If the rightmost node doesn't have a threaded connection to the current node, establish a thread connection from it to the current node and print the current node's value. Move to the left child. iii. If a thread connection already exists, remove the thread connection and move to the right child.

## Pseudocode

``````MorrisPreorder(root):
current = root
while current is not null:
if current's left child is null:
print current's value
current = current's right child
else:
auxiliary = current's left child
while auxiliary's right child is not null and auxiliary's right child is not current:
auxiliary = auxiliary's right child
if auxiliary's right child is null:
print current's value
auxiliary's right child = current
current = current's left child
else:
auxiliary's right child = null
current = current's right child
``````

## Algorithm Explanation

1. Start with the root node. Initialize `current` as the root node.
2. Traverse the tree using a `while` loop until `current` becomes null.
3. Inside the loop:

a. If the current node doesn't have a left child, print its value and move to the right child.

b. If the current node has a left child:

i. Start with `auxiliary` as the left child of the current node.

ii. Find the rightmost node in the left subtree by moving right until the right child of `auxiliary`

is null or points back to the `current` node.

iii. If the right child of the `auxiliary` node is null:

- Print the value of the `current` node.

- Establish a thread connection by setting the right child of `auxiliary` to `current`.

- Move to the left child.

iv. If the right child of `auxiliary` is the `current` node (indicating a threaded connection):

- Remove the thread connection by setting the right child of `auxiliary` to null.

- Move to the right child.

## 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 of the tree is traversed exactly twice: once while establishing the thread connections and once while removing them.

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