Problem statement

https://leetcode.com/problems/find-root-of-n-ary-tree/

Solution

Just traverse tree and find node with indegree 0. Or we can calculate size of subtree for each node and then choose the maximum one. If we you memoisation, time will be linear.

Complexity

Time and space complexity is O(n)

Code

class Solution:
    def findRoot(self, tree):
        @lru_cache(None)
        def dfs(node):
            return sum([dfs(child) for child in node.children]) + 1
        
        return max([node for node in tree], key = lambda x:dfs(x))