algoadvance

Leetcode 589. N

Problem Statement

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

N-ary tree is a rooted tree in which each node has at most N children.

For example, given a 3-ary tree:

    1
   /|\
  3 2 4
 / \
5   6

You should return [1, 3, 5, 6, 2, 4] in preorder traversal.

Note:

Clarifying Questions

  1. Input Type: What does the node structure look like?
    • The Node structure for a tree is defined as: 
      class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
  2. Tree Properties: Can the tree have nodes with no children?
    • Yes, nodes can have zero children.
  3. Edge Cases: What should be returned for an empty tree?
    • Return an empty list [].
  4. Duplicates: Can there be duplicate values in the tree?
    • Yes, nodes can have duplicate values.

Strategy

The preorder traversal visits nodes in the following order:

  1. Visit the root node.
  2. Recursively traverse each of the root’s children.

To implement this iteratively, use a stack:

  1. Start by pushing the root node onto the stack.
  2. While the stack is not empty:
    • Pop the top node.
    • Add its value to the result list.
    • Push its children onto the stack in reverse order (so that the leftmost child is processed first).

This approach ensures that nodes are processed in the correct preorder sequence.

Code

Here’s the implementation in C++:

#include <vector>
#include <stack>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> result;
        if (root == nullptr) return result;

        stack<Node*> s;
        s.push(root);

        while (!s.empty()) {
            Node* node = s.top();
            s.pop();
            result.push_back(node->val);
            // Push nodes in reverse order of their appearance.
            for (int i = node->children.size() - 1; i >= 0; --i) {
                s.push(node->children[i]);
            }
        }

        return result;
    }
};

Time Complexity

  1. Time Complexity: O(N)
    • Where N is the total number of nodes in the tree. Each node is visited exactly once.
  2. Space Complexity: O(N)
    • In the worst case, especially for a tree similar to a linked list (a degenerate tree), the stack can hold all nodes, which gives us O(N) space complexity.

This completes both the recursive and non-recursive (iterative) approaches to solving the problem of N-ary tree preorder traversal.

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