Simple Java solutions (both recursive and iterative) with explanations
I am describing both solutions since it is important to think both iteratively and recursively. Firstly, the recursive solution since that is the most common on
I am describing both solutions since it is important to think both iteratively and recursively. Firstly, the recursive solution since that is the most common one:\n\n1. Recursive solution: The idea is the same as a binary tree recursive method. It is actually like a Graph that requires DFS traversal. Go deep down a node till you reach a null node and the print the leaf node there.  The following code does exactly the same. Iterates through each child and push the one in the stack to call the postorder on it recursively. When we are in the stack returned from its children, we add the value to the list.\n\n\n```\npublic List<Integer> postorder(Node root) {\n        if (root == null) {\n            return Collections.emptyList();\n        }\n        List<Integer> newList = new ArrayList<>();\n        for(Node child : root.children) {\n            newList.addAll(postorder(child));\n        }\n        newList.add(root.val);\n        return newList;\n    }\n```\n\n2. Iterative Solution\n\nIterative solution is slightly tricky but if you have worked with the stack then you\'d know the idea is same as the recursion. Pick one child and go deep down till you don\'t find a child anymore. Since we don\'t wanna traverse the same child, we need some bookkeeping to know that we have visited that before. I created a method called geNextUnseenChild that looks at the visited set and figures out if we have any child that needs to be pursued or not. So the idea is to peek a parent and take a look at it. If you find a child to traverse, you are not going to pop the parent out yet. Once you find a parent that has no child to traverse, pop the parent out and print it. It will get us what we want.\n\n```\npublic List<Integer> postorder(Node root) {\n        if (root == null) {\n            return Collections.emptyList();\n        }\n        final List<Integer> list = new ArrayList<>(); \n        final Stack<Node> stack = new Stack<>();\n        final Set<Node> visited = new HashSet<>();\n        stack.push(root);\n        while(!stack.isEmpty()) {\n            Node parent = stack.peek();\n            Node unseenChild = getNextUnseenChild(parent, visited);\n            if (unseenChild != null) {\n                stack.push(unseenChild);\n            } else {\n                list.add(stack.pop().val);\n            }            \n        }\n        return list;\n    }\n    \n    private Node getNextUnseenChild(Node parent, Set<Node> set) {\n        for (Node child : parent.children) {\n            if (!set.contains(child)) {\n                set.add(child);\n                return child;\n            }\n        }\n        return null;\n    }\n\n```
[]