Find root of a Tree in O(n)-time, O(1)-space

Here is the problem: https://leetcode.com/problems/find-root-of-n-ary-tree/

In order to solve it in O(n)-time and O(1)-space, I did the following:
 - The fact that the numbers are unique is certainly an important cue
 - The root is the only val without a parent
 - Sum up all the parents in a variable sumParents
 - Sum up all the children in a variable sumChildren
 - Given the uniqueness of the vals, the root index will be rootIndex = sumParents - sumChildren
 - Do another O(n) pass to find the node whose val is rootIndex. Return that one

Code is below, and me on vacation below. Stay safe!!! ACC



public Node FindRoot(List<Node> tree)
{
    int sumParents = 0;
    int sumChildren = 0;

    foreach (Node node in tree)
    {
        sumParents += (node != null ? node.val : 0);

        if (node != null)
        {
            foreach (Node child in node.children)
            {
                sumChildren += (child != null ? child.val : 0);
            }
        }
    }

    int rootIndex = sumParents - sumChildren;

    foreach (Node node in tree)
    {
        if (node != null && node.val == rootIndex) return node;
    }

    return null;
}

Comments

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons