Leetcode 589: N-ary Tree Preorder Traversal

Input: The root of an n-ary tree, represented in a serialized level order format, where each node and its children are listed sequentially. Each group of children is separated by a null value.

Example: Input: root = [10, null, 20, 30, 40, null, 50, 60]

Constraints:

• 0 <= number of nodes <= 10^4

• 0 <= Node.val <= 10^4

• The height of the n-ary tree is <= 1000.

Output: A list of integers representing the nodes' values in preorder traversal order.

Example: Output: [10, 20, 50, 60, 30, 40]

Constraints:

• The output list contains integers in preorder traversal order of the tree.

Goal: Return the nodes' values in preorder traversal order.

Steps:

• Start from the root node.

• Visit the node, then recursively visit its children in left to right order.

• Return the list of visited nodes' values.

Goal: The input tree can have up to 10^4 nodes and its height can be up to 1000.

Steps:

• 0 <= number of nodes <= 10^4

• 0 <= Node.val <= 10^4

• The height of the n-ary tree is <= 1000.

Assumptions:

• The tree is represented in level order format, with groups of children separated by null.

• Input: Input: root = [10, null, 20, 30, 40, null, 50, 60]

• Explanation: Preorder traversal starts with the root node (10), followed by its children (20, 30, 40), and then recursively visits each child's children in the same manner.

• Input: 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]

• Explanation: This tree visits the root node (1), then its children (2, 3, 4), and continues recursively with the children of each node.

Approach: We can solve this problem using a recursive approach to traverse the tree in preorder.

Observations:

• Preorder traversal visits the node first and then its children.

• We can use a recursive function to perform the preorder traversal.

Steps:

• Start from the root node.

• If the node is null, return.

• Otherwise, visit the node and recursively visit each child in left-to-right order.

Empty Inputs:

• If the tree is empty (root is null), return an empty list.

Large Inputs:

• The solution should be efficient enough to handle up to 10^4 nodes.

Special Values:

• If the tree has only one node, return that node.

Constraints:

• The tree height is less than or equal to 1000, so a recursive solution should work efficiently.

vector<int> ans;
void pre(Node* root) {
    if(root == NULL) return;
    ans.push_back(root->val);
    for(auto x: root->children)
        pre(x);
}
vector<int> preorder(Node* root) {
    pre(root);
    
    return ans;
}

1 : Variable Declaration

vector<int> ans;

Declares a global variable `ans`, a vector of integers, which will store the node values in preorder during the traversal.

2 : Function Declaration

void pre(Node* root) {

Declares the recursive helper function `pre`, which takes a pointer to the root of a node in the tree and performs the preorder traversal.

3 : Base Case

    if(root == NULL) return;

Checks if the current node is null (base case). If it is, the function returns immediately without doing any further processing.

4 : Push Current Node Value

    ans.push_back(root->val);

Pushes the current node's value to the `ans` vector to record it in the preorder sequence.

5 : Recursive Traversal

    for(auto x: root->children)

Iterates over each child of the current node (since it is assumed to be a tree or n-ary tree). The function recursively calls `pre` on each child.

6 : Recursive Call

        pre(x);

Recursively calls the `pre` function on the child node `x` to traverse deeper into the tree.

7 : Function Declaration

vector<int> preorder(Node* root) {

Declares the main `preorder` function, which initializes the preorder traversal by calling the helper function `pre` and then returns the result stored in the `ans` vector.

8 : Initial Traversal Call

    pre(root);

Calls the helper function `pre` to start the preorder traversal from the root node.

9 : Return Result

    return ans;

Returns the vector `ans`, which contains the values of the nodes in preorder.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the number of nodes in the tree.

Best Case: O(h)

Worst Case: O(h)

Description: The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.

Leetcode 589: N-ary Tree Preorder Traversal

Solution to LeetCode 589: N-ary Tree Preorder Traversal Problem

Explore →