LeetCode 1506: Find Root of N-Ary Tree Solution

Master LeetCode problem 1506 (Find Root of N-Ary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1506. Find Root of N-Ary Tree

Medium

Hash Table Bit Manipulation Tree Depth-First Search

Problem Explanation

Explanation:

To find the root of an N-ary tree, we can iterate through each node in the tree and keep track of the nodes that are pointed to by other nodes. The root node will be the one that is not pointed to by any other node.

Algorithm:

Initialize a HashMap to store each node along with the count of references to that node.
Iterate through each node in the tree.
For each child node of the current node, increment the count of references in the HashMap.
After iterating through all nodes, the node with a count of references equal to 0 is the root node.

Time Complexity: O(N), where N is the number of nodes in the tree. Space Complexity: O(N) for storing nodes in the HashMap. :

Solution Code

class Solution {
    public Node findRoot(List<Node> tree) {
        Map<Node, Integer> refCount = new HashMap<>();
        
        for (Node node : tree) {
            refCount.put(node, refCount.getOrDefault(node, 0));
            for (Node child : node.children) {
                refCount.put(child, refCount.getOrDefault(child, 0) + 1);
            }
        }
        
        for (Node node : tree) {
            if (refCount.get(node) == 0) {
                return node;
            }
        }
        
        return null;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1506 (Find Root of N-Ary Tree)?

This page provides optimized solutions for LeetCode problem 1506 (Find Root of N-Ary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1506 (Find Root of N-Ary Tree)?

The time complexity for LeetCode 1506 (Find Root of N-Ary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1506 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1506 in Java, C++, or Python.

Back to LeetCode Solutions