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();
            preOrder.add(root.val);
            //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;
        //add root val
        preOrder.add(root.val);
        //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

• Introduction to N-ary Tree
• Delete a Node in a Binary Tree
• Binary Tree Preorder Traversal
• Binary Tree Postorder Traversal
• Binary Tree Level Order Traversal

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.