## Introduction

• In this article, we will solve Leetcode 589 problem which good problem to practice tree data structure
• We will also look at stack based solution for this problem along with the recursive solution.

## Problem Statement

• We have been given N-ary tree and we need to return pre-order traversal of it’s node value.
• Input tree represented has null value that is basically depicts the separation of children from parent.

## Example

• In this example , we can see input has null which means there is children for the given parent and its separated by null.
• Pre order traversal means we first cover root node then left child and then right child, but since our tree is n-ary that means we will travel from left to right for the post order.
• So pre order would be root ->left -> right children
• Below example,[1,[[3,5,6],,]]

## Solution

Intuition

• We will traverse each node, check if it’s not null then add the value to the result.
• Since now we have visited the root node we can visit children node and make a recursive call from the left child to the right child.
• That’s it. we have mad preorder traversal very easy with recursion

Code

Recursion

```/*
// Definition for a Node.
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;
}
};
*/

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

private void sol1(Node root){
if(root==null) return;
for(Node node: root.children){
sol1(node);

}
}
}

```

Stack

• we can also use stack to solve this problem. all we have to do is to keep list of children’s in stack as we visit them.
• we need to reverse children before adding to the stack since if we traverse from left to right child , our stack would have the last child on the top. so then we will be visiting in a different order.
• And then we can add them in stack and keep poping them from stack and visiting their children and so on.
• Whenever we pop the node we can add them to our result and finally we can return the result

```/*
// Definition for a Node.
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;
}
};
*/

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

private void sol2(Node root){
if(root==null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);

while(!stack.isEmpty()){
Node curr = stack.pop();
List<Node> childrens = curr.children;
Collections.reverse(childrens);
for(Node node: childrens){
stack.push(node);
}
}

}

}
```

## Result

• Our result is accepted by leetcode.

## Complexity

• 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

• In this article, we solved Leetcode 590 solution which help us to understand the n-ary tree and how we can traverse it in pre-order.
• We also discussed stack-based solutions as variations.

## Bonus Tip

• If you want to upskill your coding interview game, you can definitely check out this bestseller course ( this is in Java )