N-ary Tree preorder traversal Java

1. Overview

In this article, we will learn the preorder traversal of N-ary tree in Java. To learn more about other data structures, refer to these articles.

2. N-ary tree

The N-ary trees are a collection of nodes where each node is a data structure that comprises records and a list of references to its children. Every node store the address of its children.

The N-ary trees exhibit the following properties:

1. Every node can have multiple child nodes
2. The number of child nodes not known in advance.

Each node has the following 3 components:

1. Data element: Stores any data in the node
2. List of child nodes

A empty node is represented by the null pointer.

3. N-ary preorder traversal in Java

The Preorder traversal follows the below steps:
   1. Visit the root node.
   2. Traverse the left sub-tree such that preorder (left-subtree)
   3. Traverse the right sub-tree such that preorder (right-subtree) 

// Definition for a Node.
import java.util.*;
class Node {
    public int val;
    public List<Node> children = new ArrayList<Node>();
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class Solution {
    public static void main(String args[]) {
        Node five = new Node();
        five.val = 5;
        Node six = new Node();
        six.val = 6;
        List<Node> children = new ArrayList<Node>();
        children.add(five);
        children.add(six);
        Node three = new Node(3, children);
        Node two = new Node();
        two.val = 2;
        Node four = new Node();
        four.val = 6;
        List<Node> rootChild = new ArrayList<Node>();
        rootChild.add(three);
        rootChild.add(two);
        rootChild.add(four);
        Node root = new Node(1, rootChild);
        System.out.println(preorder(root));
    }
    public static List<Integer> preorder(Node root) {
        return traverse(new ArrayList<Integer>(), root);
    }
    private static List<Integer> traverse(List<Integer> output, Node node) {
        if (node == null) return output;
        output.add(node.val);
        for (Node child: node.children) {
            traverse(output, child);
        }
        return output;
    }
}

4. Conclusion

To sum up, we have learned the preorder traversal of the N-ary tree in Java.