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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

New Year Chaos Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala