Find Root of N-Ary Tree - Practice Coding Problems

Find Root of N-Ary Tree - Problem

You are given all the nodes of an N-ary tree as an array of Node objects, where each node has a unique value.

Return the root of the N-ary tree.

Note: The root is the only node that is not a child of any other node. All other nodes have exactly one parent.

Input & Output

Example 1 — Simple Tree

$ Input: tree = [{"val":1,"children":[3,2,4]},{"val":3,"children":[]},{"val":2,"children":[]},{"val":4,"children":[]}]

› Output: [{"val":1,"children":[3,2,4]},{"val":3,"children":[]},{"val":2,"children":[]},{"val":4,"children":[]}]

💡 Note: Node 1 has children [3,2,4]. Nodes 3, 2, 4 are children of node 1. Only node 1 is never a child of any other node, so it's the root.

Example 2 — Two Levels

$ Input: tree = [{"val":1,"children":[2,3]},{"val":2,"children":[4,5]},{"val":3,"children":[]},{"val":4,"children":[]},{"val":5,"children":[]}]

› Output: [{"val":1,"children":[2,3]},{"val":2,"children":[4,5]},{"val":3,"children":[]},{"val":4,"children":[]},{"val":5,"children":[]}]

💡 Note: Node 1 is the parent of nodes 2 and 3. Node 2 is the parent of nodes 4 and 5. Only node 1 has no parent, making it the root.

Example 3 — Single Node

$ Input: tree = [{"val":1,"children":[]}]

› Output: [{"val":1,"children":[]}]

💡 Note: Only one node exists with no children. This single node is the root by definition.

Constraints

The total number of nodes is between [1, 5 * 10⁴].
Each node has a unique value.
0 <= Node.val <= 10⁵
The input is guaranteed to be a tree (no cycles).
The input will always have exactly one root.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of nodes with their children relationships

Process

Find the node that never appears as a child

Output

Return the root node

Key Takeaway

🎯 Key Insight: The root is the only node that never appears as someone's child - track all children and find the missing one

Asked in

G Google 25 a Amazon 20 f Facebook 15 M Microsoft 12

The key insight is that the root is the only node that never appears as anyone's child. We can find it using a hash set to track children (O(n) time, O(n) space) or XOR bit manipulation to cancel out parent-child pairs (O(n) time, O(1) space). Best approach is XOR for optimal space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Hash Set	O(n)	O(n)	First pass collects all children, second pass finds the missing node
Brute Force Check	O(n²)	O(1)	Check each node to see if it's anyone's child
XOR Bit Manipulation	O(n)	O(1)	Use XOR to cancel out all parent-child pairs, leaving only the root

Two-Pass Hash Set — Algorithm Steps

First pass: Add all children to a hash set
Second pass: Find the node not in the children set
Return that node as the root

Visualization

Tap to expand

Step-by-Step Walkthrough

Pass 1: Collect Children

Add nodes 3, 2, 4 to children set

Pass 2: Check Each Node

Node 1 is not in children set

Found Root

Node 1 is the only non-child - it's the root

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct Node {
    int val;
    struct Node** children;
    int childrenSize;
};

struct Node* solution(struct Node** tree, int treeSize) {
    if (treeSize == 0) return NULL;
    
    bool* isChild = (bool*)calloc(10000, sizeof(bool));
    
    for (int i = 0; i < treeSize; i++) {
        struct Node* node = tree[i];
        for (int j = 0; j < node->childrenSize; j++) {
            isChild[node->children[j]->val] = true;
        }
    }
    
    for (int i = 0; i < treeSize; i++) {
        if (!isChild[tree[i]->val]) {
            free(isChild);
            return tree[i];
        }
    }
    
    free(isChild);
    return NULL;
}

int main() {
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two separate O(n) passes through the nodes

✓ Linear Growth

Space Complexity

O(n)

Hash set stores up to n-1 child nodes

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler