589. N-ary Tree Preorder Traversal | N-ary Tree Preorder Traversal LeetCode Solution in Java

N-ary trees, also known as k-ary trees, are tree data structures where each node can have up to ‘n’ children. They are a generalization of binary trees and are used in various applications, including file systems and hierarchical data representations. In this comprehensive blog post, we will explore the concept of N-ary trees, discuss the preorder traversal technique, and provide a Java solution for the “N-ary Tree Preorder Traversal” problem on LeetCode. We will break down the problem step by step, explain the algorithm, and provide code examples.

Understanding N-ary Trees

Before diving into N-ary tree preorder traversal, let’s make sure we have a solid understanding of N-ary trees.

An N-ary tree is a tree data structure in which each node can have up to ‘n’ children. Here’s a visual representation of a simple N-ary tree:

      1
    / | \
   3  2  4
  / \
 5   6

In this tree, 1 is the root node, and it has three children: 3, 2, and 4. Node 3 has two children, 5 and 6. Nodes 5 and 6 are leaf nodes as they have no children.

Preorder Traversal

Preorder traversal is one of the three commonly used methods to traverse a tree, alongside inorder and postorder traversal. In preorder traversal, you visit the root node first, then traverse all the children from left to right, and finally, recursively apply the preorder traversal to each child.

Let’s apply preorder traversal to the N-ary tree we discussed earlier:

Preorder Traversal: 1, 3, 5, 6, 2, 4

As you can see, we start from the root node (1), then move to its children in left-to-right order (3, 2, 4). For node 3, we continue with its children (5, 6) before moving on to node 2 and, finally, node 4.

LeetCode Problem: N-ary Tree Preorder Traversal

LeetCode is a popular platform for practicing coding problems and algorithms. The problem we’ll tackle here is known as “N-ary Tree Preorder Traversal” (Problem #589). The problem statement is as follows:

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

Example

Let’s take an example to illustrate the problem. Consider the following N-ary tree:

      1
    / | \
   3  2  4
  / \
 5   6

The preorder traversal of this tree is [1, 3, 5, 6, 2, 4].

Approach: Recursive Solution

We can solve this problem using a recursive approach. We’ll create a helper function that performs the preorder traversal and collects the node values into a list.

Here’s the Java code for this approach:

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

class Node {
    int val;
    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 NaryTreePreorderTraversal {
    public List<Integer> preorder(Node root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(Node node, List<Integer> result) {
        if (node != null) {
            result.add(node.val);
            for (Node child : node.children) {
                preorderHelper(child, result);
            }
        }
    }
}

In this code, we define a Node class to represent the nodes of the N-ary tree. Each Node has an integer value and a list of children nodes. The preorder method is the entry point for our solution. It initializes an empty list called result to store the node values and then calls the preorderHelper function to perform the actual traversal.

The preorderHelper function is a recursive function that takes two parameters: the current node (node) and the result list. It checks if the current node is not null, adds its value to the result list, and then recursively applies the preorder traversal to each child node.

Testing the Solution

To test our solution, let’s create an N-ary tree and call the preorder method to get the preorder traversal of the tree. We’ll also print the result to verify that it matches our expectations.

public class Main {
    public static void main(String[] args) {
        // Create the N-ary tree
        Node root = new Node(1);
        Node node3 = new Node(3);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);

        root.children = new ArrayList<>();
        root.children.add(node3);
        root.children.add(node2);
        root.children.add(node4);
        node3.children = new ArrayList<>();
        node3.children.add(node5);
        node3.children.add(node6);

        NaryTreePreorderTraversal solution = new NaryTreePreorderTraversal();

        // Test the solution
        List<Integer> preorderResult = solution.preorder(root);
        System.out.println("Preorder Result: " + preorderResult);
    }
}

When you run the code above, you should see the following output:

Preorder Result: [1, 3, 5, 6, 2, 4]

The solution correctly produces the preorder traversal of the N-ary tree.

Complexity Analysis

Before concluding, let’s briefly analyze the time and space complexity of our solution.

• Time Complexity: O(n), where n is the number of nodes in the N-ary tree. This is because we visit each node exactly once.
• Space Complexity: O(h), where h is the height of the N-ary tree. In the worst case, when the tree is highly unbalanced, the space complexity approaches O(n), but in a balanced tree, it is O(log n).

Conclusion

In this blog post, we explored the concept of N-ary trees and the preorder traversal technique, a fundamental method for traversing these trees. We provided a Java solution for the “N-ary Tree Preorder Traversal” problem on LeetCode. You learned how to implement the traversal recursively and correctly produced the preorder traversal of an N-ary tree.

Understanding N-ary trees and traversal techniques is valuable for various applications involving hierarchical data structures. Whether you’re preparing for coding interviews or working on projects that require tree traversal, these concepts and solutions will enhance your programming skills and problem-solving abilities.

Thank You!

Read More –

118. Pascal’s Triangle | Pascal’s Triangle LeetCode Solution in Java | Code with Kamlesh – https://kamleshsingad.com/118-pascals-triangle-pascals-triangle-leetcode-solution-in-java/

590. N-ary Tree Post order Traversal | n Array Tree Post Order Traversal LeetCode Solution in Java – https://kamleshsingad.com/590-n-ary-tree-post-order-traversal-n-array-tree-post-order-traversal/

94. Binary Tree Inorder Traversal | Binary Tree Inorder Traversal LeetCode Solution in Java – https://kamleshsingad.com/94-binary-tree-inorder-traversal-binary-tree-inorder-traversal-leetcode-solution-in-java/