Perform Postorder Tree traversal using Morris Traversal.
Examples:
Input: 1
/ \
2 3
/ \ / \
6 7 8 9Output: 6 7 2 8 9 3 1
Input: 5
/ \
2 3
/ \ / \
4 N 8 9Output: 4 2 8 9 3 5
Approach: The approach to performing Morris Traversal for Postorder is similar to Morris traversal for Preorder except swapping between left and right node links.
- Create a vector and Initialize current as root
- While current is not NULL
- If the current does not have a right child
- push the current key in vector
Go to the left, i.e., current = current->left
- push the current key in vector
- else
- Find leftmost node in current right subtree OR node whose left child == current.
- if current does not have a left child
- push the current key in the vector
- Make current as of the left child of that leftmost node
- Go to this right child, i.e., current = current->right
- else
- Found left child == current
- Update the left child as NULL of that node whose left child is current
- Go to the left, i.e. current = current->left
- If the current does not have a right child
- In the last, we reverse the vector and print it, since vector is used to store the output, the space complexity of this algorithm would be O(N).
Below is the implementation of the above approach
C++
// C++ program to perform// Morris Traversal for Postorder#include <bits/stdc++.h>using namespace std;struct TreeNode { int key; TreeNode* left; TreeNode* right; TreeNode(int data) { key = data; left = NULL; right = NULL; }};// Function to print vectorvoid print(vector<int>& ans){ // Print the vector elements for (auto x : ans) { cout << x << " "; }}// Postorder traversal// Without recursion and without stackvector<int> postorderTraversal(TreeNode* root){ vector<int> res; TreeNode* current = root; while (current != NULL) { // If right child is null, // put the current node data // in res. Move to left child. if (current->right == NULL) { res.push_back(current->key); current = current->left; } else { TreeNode* predecessor = current->right; while (predecessor->left != NULL && predecessor->left != current) { predecessor = predecessor->left; } // If left child doesn't point // to this node, then put in res // this node and make left // child point to this node if (predecessor->left == NULL) { res.push_back(current->key); predecessor->left = current; current = current->right; } // If the left child of inorder predecessor // already points to this node else { predecessor->left = NULL; current = current->left; } } } // reverse the res reverse(res.begin(), res.end()); return res;}// Driver programint main(){ TreeNode* root = new TreeNode(10); root->left = new TreeNode(20); root->right = new TreeNode(30); root->right->left = new TreeNode(40); root->right->right = new TreeNode(50); cout << "Morris(postorder) Traversal: "; vector<int> ans = postorderTraversal(root); print(ans); return 0;} |
Java
// Java program to perform// Morris Traversal for Postorderimport java.util.*;class GFG{static class TreeNode { int key; TreeNode left; TreeNode right; TreeNode(int data) { key = data; left = null; right = null; }};// Function to print vectorstatic void print(Vector<Integer> ans){ // Print the vector elements for (int x : ans) { System.out.print(x+ " "); }}// Postorder traversal// Without recursion and without stackstatic Vector<Integer> postorderTraversal(TreeNode root){ Vector<Integer> res = new Vector<>(); TreeNode current = root; while (current != null) { // If right child is null, // put the current node data // in res. Move to left child. if (current.right == null) { res.add(current.key); current = current.left; } else { TreeNode predecessor = current.right; while (predecessor.left != null && predecessor.left != current) { predecessor = predecessor.left; } // If left child doesn't point // to this node, then put in res // this node and make left // child point to this node if (predecessor.left == null) { res.add(current.key); predecessor.left = current; current = current.right; } // If the left child of inorder predecessor // already points to this node else { predecessor.left = null; current = current.left; } } } // reverse the res Collections.reverse(res); return res;} // Driver programpublic static void main(String[] args){ TreeNode root = new TreeNode(10); root.left = new TreeNode(20); root.right = new TreeNode(30); root.right.left = new TreeNode(40); root.right.right = new TreeNode(50); System.out.print("Morris(postorder) Traversal: "); Vector<Integer> ans = postorderTraversal(root); print(ans);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to perform# Morris Traversal for Postorder# class to create a new tree nodeclass TreeNode: def __init__(self, d): self.key = d self.left = None self.right = None# Function to print listdef print1(ans) : # Print the vector elements for x in ans: print(x,end=" ") # Postorder traversal# Without recursion and without stackdef postorderTraversal(root) : res=[] current = root while current != None : # If right child is None, # put the current node data # in res. Move to left child. if current.right == None : res.append(current.key) current = current.left else : predecessor = current.right while predecessor.left != None and predecessor.left != current : predecessor = predecessor.left # If left child doesn't point # to this node, then put in res # this node and make left # child point to this node if predecessor.left == None: res.append(current.key) predecessor.left = current current = current.right # If the left child of inorder predecessor # already points to this node else : predecessor.left = None current = current.left # reverse the res res.reverse() return res# Driver Codeif __name__ == '__main__': root = TreeNode(10) root.left = TreeNode(20) root.right = TreeNode(30) root.right.left = TreeNode(40) root.right.right = TreeNode(50) print("Morris(postorder) Traversal: ",end='') ans = postorderTraversal(root) print1(ans) # This code is contributed by jana_sayantan. |
C#
// C# program to perform// Morris Traversal for Postorderusing System;using System.Collections.Generic;public class GFG { public class TreeNode { public int key; public TreeNode left; public TreeNode right; public TreeNode(int data) { key = data; left = null; right = null; } }; // Function to print vector static void print(List<int> ans) { // Print the vector elements foreach (int x in ans) { Console.Write(x + " "); } } // Postorder traversal // Without recursion and without stack static List<int> postorderTraversal(TreeNode root) { List<int> res = new List<int>(); TreeNode current = root; while (current != null) { // If right child is null, // put the current node data // in res. Move to left child. if (current.right == null) { res.Add(current.key); current = current.left; } else { TreeNode predecessor = current.right; while (predecessor.left != null && predecessor.left != current) { predecessor = predecessor.left; } // If left child doesn't point // to this node, then put in res // this node and make left // child point to this node if (predecessor.left == null) { res.Add(current.key); predecessor.left = current; current = current.right; } // If the left child of inorder predecessor // already points to this node else { predecessor.left = null; current = current.left; } } } // reverse the res res.Reverse(); return res; } // Driver program public static void Main(String[] args) { TreeNode root = new TreeNode(10); root.left = new TreeNode(20); root.right = new TreeNode(30); root.right.left = new TreeNode(40); root.right.right = new TreeNode(50); Console.Write("Morris(postorder) Traversal: "); List<int> ans = postorderTraversal(root); print(ans); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to perform// Morris Traversal for Postorderclass TreeNode { constructor(data) { this.key = data; this.left = null; this.right = null; }}// Function to print vectorfunction print(ans){ // Print the vector elements for (let x of ans) { document.write(x," "); }}// Postorder traversal// Without recursion and without stackfunction postorderTraversal(root){ let res=[]; let current = root; while (current != null) { // If right child is null, // put the current node data // in res. Move to left child. if (current.right == null) { res.push(current.key); current = current.left; } else { let predecessor = current.right; while (predecessor.left != null && predecessor.left != current) { predecessor = predecessor.left; } // If left child doesn't point // to this node, then put in res // this node and make left // child point to this node if (predecessor.left == null) { res.push(current.key); predecessor.left = current; current = current.right; } // If the left child of inorder predecessor // already points to this node else { predecessor.left = null; current = current.left; } } } // reverse the res res.reverse(); return res;}// Driver programlet root = new TreeNode(10);root.left = new TreeNode(20);root.right = new TreeNode(30);root.right.left = new TreeNode(40);root.right.right = new TreeNode(50); document.write("Morris(postorder) Traversal: ");let ans = postorderTraversal(root); print(ans);// This code is contributed by shinjanpatra</script> |
Output
Morris(postorder) Traversal: 20 40 50 30 10
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
