N-ary Tree Preorder Traversal

Given the root of an n-ary tree, return the preorder traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal. Each group of children is separated by the null value (See the below examples):

Example 1:

N-Ary Tree
Input: root = [1,null,3,2,4,null,5,6]
Output: [1,3,5,6,2,4]

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,
               null,9,10,null,null,11,null,12,null,
               13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

First of all, here is the definition of the tree Node which we would use in the following implementation.

// 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;
  }
}

Let’s start from the root and then at each iteration pop the current node out of the stack and push its child nodes. In the implemented strategy we add nodes into output list by following the order Top->Bottom and Left->Right, that naturally reproduces preorder traversal.

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<Node> stack = new Stack<>();
        stack.add(root);
        
        while (!stack.isEmpty()) {
            Node curr = stack.pop();
            result.add(curr.val);
            for (int i = curr.children.size() - 1; i >= 0; i--) {
                stack.push(curr.children.get(i));
            }
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity : we visit each node exactly once, and for each visit, the complexity of the operation (i.e. appending the child nodes) is proportional to the number of child nodes n (n-ary tree). Therefore the overall time complexity is O(N), where N is the number of nodes, i.e. the size of tree.
  • Space Complexity : Depending on the tree structure, we could keep up to the entire tree, therefore, the space complexity is O(N). The output list does not comes under the space complexity considerations.

Following is a recursive solution:

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        traversePreOrder(root, result);
        return result;
    }
    
    private void traversePreOrder(Node root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val);
        for (Node child : root.children) traversePreOrder(child, result);
    }
}

Categories: N-Ary Tree

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s