Morris Postorder Traversal

Postorder traversal with no recursion

Introduction

Morris Postorder Traversal provides a space-efficient way to traverse nodes in postorder sequence, avoiding recursion or a stack and utilizing threading for O(1) space complexity.

How Morris Postorder works?

1

Start with the Root Node

  • Begin at the root node of the tree.
2

Find the Postorder Predecessor

  • For each node, find the postorder predecessor.
3

Create Temporary Link

  • Create a temporary link from the predecessor’s right child to the current node.
4

Move to Left Child

  • Move to the left child if it exists.
5

Visit the Current Node

  • Visit the current node after completing both left and right child traversal.
6

Break the Link

  • Break the temporary link when returning to the root after visiting its children.
7

Repeat

  • Continue until all nodes are visited.

Implementation of Level Order Traversal (BFS)

//morrispostorder.cpp
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void morrispostorder(Node *root,vector<int> &ans)
{
Node *curr = root;
while (curr)
{
    if (!curr->right)
    {
        ans.push_back(curr->data);
        curr = curr->left;
    }
    else
    {
        ans.push_back(curr->data);
        Node *rightchild = curr->right;
        while (rightchild->left)
        {
            rightchild = rightchild->left;
        }
        rightchild->left = curr->left;
        Node *temp = curr;
        curr = curr->right;
        temp->right = NULL;
    }
}

}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// morris postorder
vector<int> ans;
morrispostorder(root,ans);
reverse(ans.begin(),ans.end());
for(int &ele:ans){
    cout<<ele<<" ";
}
}

Time Complexity

  • Each node is visited once. During each visit, we find its inorder predecessor and create temporary links, which are all constant-time operations. So, the total time complexity is O(n), where n is the number of nodes in the tree.
  • Time Complexity:O(n)

Space Complexity

  • Space for Output: We use a vector<int> to store the result of the traversal, which takes O(n) space, as each node’s value is added to the vector.
  • Space Complexity:O(n)