### Preorder Traversal of N-ary Tree - The Coding Shala

Last Updated: 26-Jan-2021
Home >> Data Structures >> Preorder Traversal of N-ary Tree

In this post, we will learn how to traverse the N-ary Tree in Preorder and will write a Java program for Preorder Traversal.

## Preorder Traversal of N-ary Tree

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

For example, given a 3-ary tree:

1
/  |  \
3  2  4
/ \
5   6
Return its preorder traversal as: [1,3,5,6,2,4].

## Preorder Traversal of N-ary Tree Java Program

Approach 1

Iterative Solution.[Using Stack]

• step 1. check root if null.
• step 2. push root to stack
• step 3. while the stack is not empty
• step 4. add root val to answer and push all the children to the stack in reverse order.
• step 5. repeat step 3.

Java Program:

```/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> preOrder = new ArrayList<Integer>();
if(root == null) return preOrder;
Stack<Node> st = new Stack<Node>();
st.push(root);
while(!st.empty() && root != null){
root = st.pop();
//add all the children to the stack
int size = root.children.size();
for(int i = size-1; i>=0; i--) st.push(root.children.get(i));
}
return preOrder;
}
}
```

Approach 2

Using recursion.

• step 1. if root null then terminates the recursion.
• step 2. add root val to the list.
• step 3. call recursively for all the children.
Java Program:

```/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
List<Integer> preOrder = new ArrayList<Integer>();
public List<Integer> preorder(Node root) {
if(root == null) return preOrder;
//recursion for all children
for(int i=0; i<root.children.size(); i++){
preorder(root.children.get(i));
}
return preOrder;
}
}
```

Other Posts You May Like