Blog

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.

Bonus Tip

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