N-ary Tree Preorder Traversal — Leetcode 589

  • Post last modified:November 9, 2022
  • Reading time:3 mins read

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],[2],[4]]]

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;
        result.add(root.val);
        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();
            result.add(curr.val);
            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.

Leave a Reply