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 Create a Simple Calculator - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

LeetCode - Shuffle the Array Solution - The Coding Shala

Introduction to Kotlin Programming Language for Backend Development - The Coding Shala