N Ary Tree Preorder Traversal - Leetcode Solution

Problem Statement:

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

N-ary Tree Definition:

An N-ary tree is a tree in which each node can have at most n children. The tree is called an N-ary tree if every node has at most n children. The node which does not have any parent is called the root of the tree.

Preorder Traversal Definition:

Preorder traversal is a type of tree traversal algorithm that visits the root node first, followed by its left subtree, and then its right subtree. In other words, it visits the node in the order: root -> left subtree -> right subtree.

Example:

Input: 1 / |
3 2 4 /
5 6

Output: [1,3,5,6,2,4]

Solution:

The solution to this problem can be achieved using recursive approach. Before that let's first define the Node structure and a sample tree to better understand our approach.

class Node { public int val; public List<Node> children;

public Node() {}

public Node(int _val) {
    val = _val;
}
public Node(int _val, List<Node> _children) {
    val = _val;
    children = _children;
}

}

Node tree = new Node(1, Arrays.asList(new Node(3, Arrays.asList(new Node(5), new Node(6))), new Node(2), new Node(4)));

Here, we are creating a n-ary tree with root as 1 and children as 3,2 and 4. 3 has children 5 and 6. Let's try to print the values of the tree in pre-order sequence using recursion.

Approach:

• Define a new ArrayList to store the values in preorder sequence.
• Define a helper function called preorder which is used for recursive approach. This function takes a Node as an input and returns nothing.
• Add the value of the current Node to the list.
• For each child of the current node, recursively call the preorder function.
• Return the list.

Code:

class Solution { public List<Integer> preorder(Node root) { List<Integer> list = new ArrayList<>(); preorder(root, list); return list; }

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

}

Time Complexity:

O(N), where N is the number of nodes in the tree.

Space Complexity:

O(H), where H is the height of the tree.

Conclusion:

By using recursion, we can solve this problem in a simple and efficient manner. We define a helper function for recursive approach which uses preorder traversal to store every node value in the list and return it.

1