Posted on by Kalkicode
Code Binary Tree

# Morris traversal for Postorder

Morris Traversal is an efficient method for traversing binary trees without using any additional space for stacks or recursion. In this specific case, the postorder traversal of the binary tree is achieved using the Morris Traversal technique.

## Problem Statement and Description

Given a binary tree, the goal is to traverse its nodes in a postorder sequence using the Morris Traversal technique. Postorder traversal involves visiting the left subtree, then the right subtree, and finally the root node.

## Example

Consider the following binary tree:

``````
4
/   \
8     3
/ \   / \
1   6 7   2
/   \   \
9     10  11``````

The goal is to perform postorder traversal on this tree using Morris Traversal.

## Idea to Solve

The Morris Traversal algorithm utilizes threaded binary trees to achieve efficient traversal without using additional memory. In your case, for postorder traversal, the key idea is to reverse the right pointers of nodes while traversing the tree in a modified form of the pre-order traversal. This allows you to visit nodes in the required order while maintaining the tree's original structure.

## Pseudocode

Here's a high-level pseudocode representation of the algorithm:

``````class TreeNode
properties: data, left, right

class BinaryTree
properties: root

function morrisPostorder
if root is null
return

create a dummy node with value 0 and set its left child to root
current = dummy_node
while current is not null
if current.left is null
// No left child, move to right child
current = current.right
else
// Find the rightmost node in the left subtree
auxiliary = current.left
while auxiliary.right is not null and auxiliary.right is not current
auxiliary = auxiliary.right

if auxiliary.right is null
// Set right pointer to current and move to left child
auxiliary.right = current
current = current.left
else
// Reverse right pointers and traverse back from rightmost node
print_nodes_and_reverse(current.left, auxiliary)
auxiliary.right = null
current = current.right

print result (postorder traversal)

function print_nodes_and_reverse(from_node, to_node)
reverse_right_pointers(from_node, to_node)
current = to_node
while true
print current.data
if current is from_node
break
current = current.right

function reverse_right_pointers(from_node, to_node)
if from_node is to_node
return
current = from_node
prev = null
while current is not to_node
next = current.right
current.right = prev
prev = current
current = next

function main
create a new BinaryTree called "tree"
// Construct tree here

print "Morris Postorder:"
tree.morrisPostorder()``````

## Algorithm Explanation

The algorithm starts by initializing the `dummy_node` to aid in traversal. It then iterates through the tree while reversing and restoring the right pointers of nodes as needed. When encountering a node with no left child, it moves to the right child. When encountering a node with a left child, it finds the rightmost node of the left subtree, reverses the right pointers from the left child to the rightmost node, and then traverses back, printing nodes in the postorder sequence.

## 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 node is visited at most twice: once when traversing down the tree and once when traversing back up. The algorithm avoids the need for an explicit stack, reducing the space complexity to O(1).

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