589. N-ary Tree Preorder Traversal

/**

 * 589. N-ary Tree Preorder Traversal

 * Given an n-ary tree, return the preorder 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: [1,3,5,6,2,4]

 */

See the solution at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/n_array/PreOrder.java

Observation: This is similar to the post order traversal solution to which is also available here. Here we are traversing the tree in pre order fashion. Thus, each element visited must be added as next in output. We could use a stack here and add elements to end of a list. For each node visited we want to add its elements back on stack. But children of a node will be in order left to right, we want the left most children on top of stack thus we reverse the order of children of a node, before adding children back on stack.

Here is the code:

public List<Integer> preorder(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }
    while (!stack.isEmpty()) {
        Node node = stack.pop();
        list.add(node.val);
        List<Node> nodes = new LinkedList<>(node.children);
        Collections.reverse(nodes); //reverse because you want the left most child to be on top of stack
        stack.addAll(nodes);
    }
    return list;
}