algoadvance

Problem Statement

You are given an n-ary tree. Implement the preorder traversal. The n-ary tree is represented by its root node. Implement a function preorder(Node root) that returns a list of node values in pre-order traversal.

Example:

          1
       /  |  \
      3   2   4
     / \
    5   6

Input: root = [1,[3,[5,6],2,4]]
Output: [1,3,5,6,2,4]

Note: The format in the input example is the tree’s root node followed by its children, the children’s children, and so on, in the form of an array list.

Clarifying Questions

Q: Can the tree be empty? A: Yes, the tree can be empty, in which case the root will be null and the function should return an empty list.
Q: Will the tree contain only integer values? A: For the sake of this problem, yes, you can assume the node values are integers.

Strategy

To solve this problem, we can use a Depth-First Search (DFS) approach since Preorder traversal follows the sequence: root -> children.

We can implement this using either a recursive or an iterative approach.

Recursive Approach: Define a helper method that visits a node, adds its value to the result list, and then recursively visits each of its children.
Iterative Approach: Use a stack to simulate the call stack of recursion. Push nodes onto the stack, pop them to visit, and push their children in reverse order to ensure the left-most child is processed first.

Time Complexity

Both the recursive and iterative approaches have a time complexity of O(n), where n is the number of nodes in the tree, because we visit each node exactly once.
The space complexity is O(n) in both cases due to the call stack used in recursion or the stack used in iteratively traversing the tree.

Code

We will implement both the recursive and iterative solutions:

Recursive Approach

import java.util.ArrayList;
import java.util.List;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int val) {
        this.val = val;
    }

    public Node(int val, List<Node> children) {
        this.val = val;
        this.children = children;
    }
}

public class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        helper(root, result);
        return result;
    }

    private void helper(Node node, List<Integer> result) {
        if (node == null) {
            return;
        }
        
        // Add the root node value
        result.add(node.val);
        
        // Recursively visit all children
        for (Node child : node.children) {
            helper(child, result);
        }
    }
}

Iterative Approach

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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

Both implementations correctly solve the problem, enabling the traversal of an n-ary tree in preorder manner.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?