1. Introduction

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

This article is part of Binary Tree-Traversals. Read more about Binary Tree traversals here.

2. Content

I have explained Preorder traversal in Binary Tree in this article. I would recommend you to read that first.

We can do Preorder traversal in n-ary tree:

1. Visit the root node
2. Recursively traverse its children

Preorder Traversal Result: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

3. Preorder using Recursion

Recursion code is very simple. We will visit the root node, if it is not null and then recurse for its children one after another.

public List<Integer> preorder(Node root) {
   if (root == null) return List.of();
   List<Integer> list = new ArrayList<>();
   preorder(root, list);
   return Collections.unmodifiableList(list);
}

private void preorder(Node root, List<Integer> list) {
   if (root != null) {
       list.add(root.val);
       for (Node n : root.children) {
           preorder(n, list);
       }
   }
}

Time and Space complexity nomenclature: n where n is the total number of nodes in the tree.

Time Complexity: O(n) because we traverse the entire tree.

Space Complexity: O(n) because we save all the nodes in the auxiliary result.

4. Preorder using Iteration

Preorder traversal using Iteration is also very easy. 

1. Let us start with the most basic case. If the root node is null, we return an empty list.

public List<Integer> preorder(Node root) {

    if (root == null) return List.of();

}

2. Initialize the result and the stack.

public List<Integer> preorder(Node root) {
        if (root == null) return List.of();
        
        List<Integer> result = new ArrayList<>();
        
        Deque<Node> stack = new ArrayDeque<>();
        stack.add(root);       
}

3. While the stack is not empty, pop the node from it and insert the children of this node. Insert the children in reverse as we want to traverse the tree left to right.

while (!stack.isEmpty()) {
    Node curr = stack.pop();
    result.add(curr.val);
    for (int i = curr.children.size() - 1; i >= 0; i--) {
        stack.push(curr.children.get(i));
    }
}

Entire implementation:

public List<Integer> preorder(Node root) {
    if (root == null) return List.of();
        
    List<Integer> result = new ArrayList<>();
        
    Deque<Node> stack = new ArrayDeque<>();
    stack.add(root);
        
    while (!stack.isEmpty()) {
        Node curr = stack.pop();
        result.add(curr.val);
        for (int i = curr.children.size() - 1; i >= 0; i--) {
            stack.push(curr.children.get(i));
        }
    }
    return result;
}

Time Complexity: O(n) because we traverse the entire tree.

Space Complexity: O(n) because we save all the nodes in the auxiliary result.

5. Conclusion:

In this article, we saw Preorder Traversal of the n-ary Tree using Recursion and Iteration.

GitHub link: https://github.com/savanibharat/justamonad-tutorials/blob/master/justamonad-tutorials-leetcode/src/main/java/com/justamonad/tutorials/leetcode/tree/NAryTreePreorderTraversal.java