algoadvance

Leetcode 429. N

Problem Statement

Given an n-ary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example:

Input: [1,null,3,2,4,null,5,6]

Explanation:

   1
 / | \
3  2  4    / \   5   6

Output: [[1], [3,2,4], [5,6]]

Clarifying Questions

  1. Input Format: How is the input provided? Is it a list representation or a tree structure?
    • The input is generally provided as a tree structure, where each node contains a value and a list of child nodes.
  2. Node Definition: How is an N-ary tree node defined?
    • An N-ary tree node typically contains a value and a list of its child nodes.
  3. Edge Cases: What are the edge cases we need to consider?
    • An empty tree (null root).
    • A tree with only one node.
    • Skewed tree (tree that looks more like a linked list).

Code

Strategy

  1. Breadth-First Search (BFS): Use a queue to perform a level order traversal.
  2. Queue Initialization: Start by adding the root node to the queue.
  3. Process Nodes Level by Level:
    • While the queue is not empty, process each level by iterating over the number of nodes currently in the queue (since they all belong to the same level).
    • Collect the values of the nodes at the current level and add their children to the queue for the next level.

Algorithm:

Implementation:

import java.util.*;

// Node definition for an N-ary tree
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

public class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();
                level.add(current.val);
                for (Node child : current.children) {
                    queue.offer(child);
                }
            }

            result.add(level);
        }

        return result;
    }

    public static void main(String[] args) {
        // Example usage:
        Node node5 = new Node(5, new ArrayList<>());
        Node node6 = new Node(6, new ArrayList<>());
        
        List<Node> children3 = new ArrayList<>(Arrays.asList(node5, node6));
        Node node3 = new Node(3, children3);

        Node node2 = new Node(2, new ArrayList<>());
        Node node4 = new Node(4, new ArrayList<>());
        
        List<Node> children1 = new ArrayList<>(Arrays.asList(node3, node2, node4));
        Node root = new Node(1, children1);

        Solution solution = new Solution();
        List<List<Integer>> result = solution.levelOrder(root);
        System.out.println(result);  // Output: [[1], [3, 2, 4], [5, 6]]
    }
}

Time Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the tree. This is because we visit each node exactly once during the BFS traversal.

Space Complexity

The space complexity is O(N) for the queue used in the BFS traversal, where N is the number of nodes. This is because, in the worst case, the queue will hold all the nodes at the current level before advancing to the next level.

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