Iterative Postorder Traversal of N-ary Tree
Given an N-ary tree, the task is to find the post-order traversal of the given tree iteratively.
Examples:
Input: 1 / | \ 3 2 4 / \ 5 6 Output: [5, 6, 3, 2, 4, 1] Input: 1 / \ 2 3 Output: [2, 3, 1]
Approach:
We have already discussed iterative post-order traversal of binary tree using one stack. We will extend that approach for the n-ary tree. The idea is very simple, for every node we have to traverse all the children of this node (from left to right) before traversing the node.
Pseudo Code:
- Start from the root.
- Repeat all the steps below till either root != null OR stack is not empty.
- If root != null then push root and it’s an index into the stack and continues towards the left node.
- Pop the element from the stack and print it.
- Pop all the elements from stack till stack is not empty && popped node is last children of
it’s a parent. - Assign root to the next children of top of stack’s node.
Below is the implementation of the above approach:
C++
// C++ Program to iterative Postorder // Traversal of N-ary Tree #include<bits/stdc++.h> using namespace std; // Node class class Node { public : int val; vector<Node*> children ; // Default constructor Node() {} Node( int _val) { val = _val; } Node( int _val, vector<Node*> _children) { val = _val; children = _children; } }; // Helper class to push node and it's index // into the st class Pair { public : Node* node; int childrenIndex; Pair(Node* _node, int _childrenIndex) { node = _node; childrenIndex = _childrenIndex; } }; // We will keep the start index as 0, // because first we always // process the left most children int currentRootIndex = 0; stack<Pair*> st; vector< int > postorderTraversal ; // Function to perform iterative postorder traversal vector< int > postorder(Node* root) { while (root != NULL || st.size() > 0) { if (root != NULL) { // Push the root and it's index // into the st st.push( new Pair(root, currentRootIndex)); currentRootIndex = 0; // If root don't have any children's that // means we are already at the left most // node, so we will mark root as NULL if (root->children.size() >= 1) { root = root->children[0]; } else { root = NULL; } continue ; } // We will pop the top of the st and // push_back it to our answer Pair* temp = st.top(); st.pop(); postorderTraversal.push_back(temp->node->val); // Repeatedly we will the pop all the // elements from the st till popped // element is last children of top of // the st while (st.size() > 0 && temp->childrenIndex == st.top()->node->children.size() - 1) { temp = st.top(); st.pop(); postorderTraversal.push_back(temp->node->val); } // If st is not empty, then simply assign // the root to the next children of top // of st's node if (st.size() > 0) { root = st.top()->node->children[temp->childrenIndex + 1]; currentRootIndex = temp->childrenIndex + 1; } } return postorderTraversal; } // Driver Code int main() { Node* root = new Node(1); root->children.push_back( new Node(3)); root->children.push_back( new Node(2)); root->children.push_back( new Node(4)); root->children[0]->children.push_back( new Node(5)); root->children[0]->children.push_back( new Node(6)); vector< int > v = postorder(root); for ( int i = 0; i < v.size(); i++) cout << v[i] << " " ; } // This code is contributed by Arnab Kundu |
Java
import java.util.*; public class GFG { // Node class static class Node { public int val; public List<Node> children = new ArrayList<Node>(); // Default constructor public Node() {} public Node( int _val) { val = _val; } public Node( int _val, List<Node> _children) { val = _val; children = _children; } }; // Helper class to push node and it's index // into the stack static class Pair { public Node node; public int childrenIndex; public Pair(Node _node, int _childrenIndex) { node = _node; childrenIndex = _childrenIndex; } } // We will keep the start index as 0, // because first we always // process the left most children int currentRootIndex = 0 ; Stack<Pair> stack = new Stack<Pair>(); ArrayList<Integer> postorderTraversal = new ArrayList<Integer>(); // Function to perform iterative postorder traversal public ArrayList<Integer> postorder(Node root) { while (root != null || !stack.isEmpty()) { if (root != null ) { // Push the root and it's index // into the stack stack.push( new Pair(root, currentRootIndex)); currentRootIndex = 0 ; // If root don't have any children's that // means we are already at the left most // node, so we will mark root as null if (root.children.size() >= 1 ) { root = root.children.get( 0 ); } else { root = null ; } continue ; } // We will pop the top of the stack and // add it to our answer Pair temp = stack.pop(); postorderTraversal.add(temp.node.val); // Repeatedly we will the pop all the // elements from the stack till popped // element is last children of top of // the stack while (!stack.isEmpty() && temp.childrenIndex == stack.peek().node.children.size() - 1 ) { temp = stack.pop(); postorderTraversal.add(temp.node.val); } // If stack is not empty, then simply assign // the root to the next children of top // of stack's node if (!stack.isEmpty()) { root = stack.peek().node.children.get( temp.childrenIndex + 1 ); currentRootIndex = temp.childrenIndex + 1 ; } } return postorderTraversal; } // Driver Code public static void main(String[] args) { GFG solution = new GFG(); Node root = new Node( 1 ); root.children.add( new Node( 3 )); root.children.add( new Node( 2 )); root.children.add( new Node( 4 )); root.children.get( 0 ).children.add( new Node( 5 )); root.children.get( 0 ).children.add( new Node( 6 )); System.out.println(solution.postorder(root)); } } |
Python3
# Python Program to iterative # Postorder Traversal of N-ary Tree # Node class class Node: def __init__( self ,_val): self .val = _val self .children = [] # Helper class to.append node and it's index # into the stack class Pair: def __init__( self ,_node, _childrenIndex): self .node = _node self .childrenIndex = _childrenIndex # We will keep the start index as 0, # because first we always # process the left most children currentRootIndex = 0 stack = [] postorderTraversal = [] # Function to perform iterative postorder traversal def postorder(root): global currentRootIndex global stack global postorderTraversal while (root ! = None or len (stack) ! = 0 ): if (root ! = None ): # append the root and it's index # into the stack stack.append(Pair(root, currentRootIndex)) currentRootIndex = 0 # If root don't have any children's that # means we are already at the left most # node, so we will mark root as None if ( len (root.children) > = 1 ): root = root.children[ 0 ] else : root = None continue # We will.Pop the top of the stack and #.append it to our answer temp = stack.pop() postorderTraversal.append(temp.node.val) # Repeatedly we will the.Pop all the # elements from the stack till.Popped # element is last children of top of # the stack while ( len (stack) ! = 0 and temp.childrenIndex = = len (stack[ - 1 ].node.children) - 1 ): temp = stack[ - 1 ] stack.pop() postorderTraversal.append(temp.node.val) # If stack is not empty, then simply assign # the root to the next children of top # of stack's node if ( len (stack) ! = 0 ): root = stack[ - 1 ].node.children[temp.childrenIndex + 1 ] currentRootIndex = temp.childrenIndex + 1 return postorderTraversal # Driver Code root = Node( 1 ) root.children.append(Node( 3 )) root.children.append(Node( 2 )) root.children.append(Node( 4 )) root.children[ 0 ].children.append(Node( 5 )) root.children[ 0 ].children.append(Node( 6 )) print ( "[" ,end = "") temp = postorder(root) size = len (temp) count = 0 for v in temp: print (v,end = "") count + = 1 if (count < size): print ( "," ,end = " " ) print ( "]" ) # This code is contributed by shinjanpatra |
C#
// C# Program to iterative Postorder Traversal of N-ary Tree using System; using System.Collections.Generic; class GFG { // Node class public class Node { public int val; public List<Node> children = new List<Node>(); // Default constructor public Node() {} public Node( int _val) { val = _val; } public Node( int _val, List<Node> _children) { val = _val; children = _children; } }; // Helper class to.Push node and it's index // into the stack class Pair { public Node node; public int childrenIndex; public Pair(Node _node, int _childrenIndex) { node = _node; childrenIndex = _childrenIndex; } } // We will keep the start index as 0, // because first we always // process the left most children int currentRootIndex = 0; Stack<Pair> stack = new Stack<Pair>(); List< int > postorderTraversal = new List< int >(); // Function to perform iterative postorder traversal public List< int > postorder(Node root) { while (root != null || stack.Count != 0) { if (root != null ) { // Push the root and it's index // into the stack stack.Push( new Pair(root, currentRootIndex)); currentRootIndex = 0; // If root don't have any children's that // means we are already at the left most // node, so we will mark root as null if (root.children.Count >= 1) { root = root.children[0]; } else { root = null ; } continue ; } // We will.Pop the top of the stack and //.Add it to our answer Pair temp = stack.Pop(); postorderTraversal.Add(temp.node.val); // Repeatedly we will the.Pop all the // elements from the stack till.Popped // element is last children of top of // the stack while (stack.Count != 0 && temp.childrenIndex == stack.Peek().node.children.Count - 1) { temp = stack.Pop(); postorderTraversal.Add(temp.node.val); } // If stack is not empty, then simply assign // the root to the next children of top // of stack's node if (stack.Count != 0) { root = stack.Peek().node.children[temp.childrenIndex + 1]; currentRootIndex = temp.childrenIndex + 1; } } return postorderTraversal; } // Driver Code public static void Main(String[] args) { GFG solution = new GFG(); Node root = new Node(1); root.children.Add( new Node(3)); root.children.Add( new Node(2)); root.children.Add( new Node(4)); root.children[0].children.Add( new Node(5)); root.children[0].children.Add( new Node(6)); Console.Write( "[" ); List< int > temp = solution.postorder(root); int size = temp.Count; int count = 0; foreach ( int v in temp) { Console.Write(v); count++; if (count < size) Console.Write( ", " ); } Console.Write( "]" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript Program to iterative // Postorder Traversal of N-ary Tree // Node class class Node { constructor(_val) { this .val = _val; this .children = []; } }; // Helper class to.Push node and it's index // into the stack class Pair { constructor(_node, _childrenIndex) { this .node = _node; this .childrenIndex = _childrenIndex; } } // We will keep the start index as 0, // because first we always // process the left most children var currentRootIndex = 0; var stack = []; var postorderTraversal = []; // Function to perform iterative postorder traversal function postorder(root) { while (root != null || stack.length != 0) { if (root != null ) { // Push the root and it's index // into the stack stack.push( new Pair(root, currentRootIndex)); currentRootIndex = 0; // If root don't have any children's that // means we are already at the left most // node, so we will mark root as null if (root.children.length >= 1) { root = root.children[0]; } else { root = null ; } continue ; } // We will.Pop the top of the stack and //.push it to our answer var temp = stack.pop(); postorderTraversal.push(temp.node.val); // Repeatedly we will the.Pop all the // elements from the stack till.Popped // element is last children of top of // the stack while (stack.length != 0 && temp.childrenIndex == stack[stack.length-1].node.children.Count - 1) { temp = stack.pop(); postorderTraversal.push(temp.node.val); } // If stack is not empty, then simply assign // the root to the next children of top // of stack's node if (stack.length != 0) { root = stack[stack.length-1].node.children[temp.childrenIndex + 1]; currentRootIndex = temp.childrenIndex + 1; } } return postorderTraversal; } // Driver Code var root = new Node(1); root.children.push( new Node(3)); root.children.push( new Node(2)); root.children.push( new Node(4)); root.children[0].children.push( new Node(5)); root.children[0].children.push( new Node(6)); document.write( "[" ); var temp = postorder(root); var size = temp.length; var count = 0; for ( var v of temp) { document.write(v); count++; if (count < size) document.write( ", " ); } document.write( "]" ); </script> |
Output:
[5, 6, 3, 2, 4, 1]
Time complexity: O(n) where n is no of nodes in a binary tree
Auxiliary space : O(n) because using vector and stack