N-ary Tree Postorder Traversal- Easy

Easy : https://leetcode.com/problems/n-ary-tree-postorder-traversal/submissions/

Given an n-ary tree, return the postorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Follow up:

Recursive solution is trivial, could you do it iteratively?

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

• The height of the n-ary tree is less than or equal to 1000
• The total number of nodes is between [0, 10^4]

Solution:

Based on the Post order traversal using stack from https://takeitoutamber.medium.com/tree-recursive-traversals-e5fdfc17e646

Strategy:

1. Push the children from right, take it to the leftmost child. Before pushing that leftmost child, push the node, then move node’s pointer to leftmost child.

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        ## Leftmost, right and then node.
        ## I just read the post order traversal using the stack so I will use that first
        ## then I will try doing it recursively. 12:19 pm.
        
        res = []
        stack = []
        node = root
        print(root.children)
        
        # when both node and stack are null, we will stop traversing
        while node or stack:
            while node:
                # push all the children from right onto the stack,
                for i in range(num_of_children-1,0,-1):
                     stack.append(node.children[i])
                
                # now push the parent
                stack.append(node)
                if node.children:
                    # if there are any children, 
                    # lets traverse them first, 
                    # starting with the 0th element.
                    node = node.children[0]
                else:
                    break
            
            # pop out the topmost node
            node = stack.pop()
            print("popped top", node.val)
            # make sure that before we process the node, all its children are processed.
            if stack and stack[-1] in node.children:
                # move the child to the top and push back the node
                child = stack[-1]
                stack[-1] = node
                node = child
            else:
                # process the node now. Either it has no children or all of its children are processed now.
                res.append(node.val)
                node = None
                
        return res

Time complexity is O(n) and space complexity is O(n)

Recursive solution is easy.

class Solution:
        def __init__(self):
            self.res = []
            
        def postorder(self, root: 'Node') -> List[int]:
            ## Leftmost, right and then node.
            ## I just read the post order traversal using the stack so I will use that first
            ## then I will try doing it recursively. 1 pm.
            # recursive
            node = root
            if root:
                # num_of_children = len(node.children)
                for child in node.children:
                    self.postorder(child)
# process the node
                self.res.append(node.val)
                
            return self.res