Jobs

Interviews

Discussions

Find Root of N-Ary Tree

Medium

Asked by:

4 views

Topics:

Trees

You are given a n-ary tree of depth n. Each node has a unique value from 1 to n.

You are also given a list of n - 1 Edges. Each Edge contains the values of two different nodes. Your task is to find the root of the n-ary tree.

Example:

Input: edges = [[1,2],[1,3],[1,4],[1,5],[2,6],[2,7]]
Output: 1

Explanation:

Given the edges:

The root of the tree is the node with value 1 since it doesn't have any parent.

Follow up:

Can you find the root in O(n) time and O(1) space?

Constraints:

n == edges.length + 1
1 <= n <= 10⁵
1 <= Node.val <= n
Each Node.val is unique.
The given edges represent a valid n-ary tree.

Try coding it in LeetCode

Find Root of N-Ary Tree

Medium

Asked by:

4 views

Topics:

Trees

You are given a n-ary tree of depth n. Each node has a unique value from 1 to n.

You are also given a list of n - 1 Edges. Each Edge contains the values of two different nodes. Your task is to find the root of the n-ary tree.

Example:

Input: edges = [[1,2],[1,3],[1,4],[1,5],[2,6],[2,7]]
Output: 1

Explanation:

Given the edges:

The root of the tree is the node with value 1 since it doesn't have any parent.

Follow up:

Can you find the root in O(n) time and O(1) space?

Constraints:

n == edges.length + 1
1 <= n <= 10⁵
1 <= Node.val <= n
Each Node.val is unique.
The given edges represent a valid n-ary tree.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty (null or zero nodes)? What should be returned in that case?
What is the data type of the node's value and is there a range for these values?
Can nodes have a maximum number of children, or is the number of children unbounded?
Is the tree guaranteed to have a single root node, or is it possible to have disconnected components or no root at all?
Are the node objects distinct, or is it possible to have multiple nodes with the same value but different object identities?

Brute Force Solution

Approach

We have a tree where each node can have many children, and we need to find the very top node, which we call the root. The brute force way is to check every node to see if it could be the root, by seeing if anyone claims it as their child.

Here's how the algorithm would work step-by-step:

Start by picking the first node in the list.
Go through all the other nodes to see if any of them point to our selected node as their child.
If no other node lists our selected node as a child, it might be the root, so we remember it.
Repeat these steps for every other node in the list.
After checking all the nodes, look at the ones we remembered as possible roots.
If we only have one possible root, then that's our answer. If we have multiple possible roots, then we can pick any of them since it means the input was invalid.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def find_root_brute_force(nodes):
    possible_roots = []

    for current_node in nodes:
        is_child = False
        for other_node in nodes:
            if current_node != other_node:
                if current_node in other_node.children:
                    is_child = True
                    break

        # Only add node to possible roots if no parent
        if not is_child:
            possible_roots.append(current_node)

    # Ensures that the edge cases work correctly
    if len(possible_roots) == 1:
        return possible_roots[0]
    elif len(possible_roots) > 0:
        return possible_roots[0]

    return None

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n nodes in the input list, considering each as a potential root. For each potential root, it then iterates through the remaining n-1 nodes to check if any of these nodes identify the potential root as a child. Thus, we have a nested loop structure where the outer loop runs n times, and the inner loop runs approximately n times for each iteration of the outer loop. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N) – The plain English solution suggests remembering potential root nodes. This implies using a data structure, likely a list or set, to store these candidates. In the worst case, all N nodes could be potential roots until proven otherwise, resulting in a list of size N. Therefore, the auxiliary space used grows linearly with the number of nodes, N, in the tree. The space complexity is O(N).

Optimal Solution

Approach

The key is to realize that every node in the tree, except the root, is pointed to by its parent. We can use this fact to quickly identify the root. By summing all node values and subtracting the sums of all child node values, the remaining value will correspond to the root node's value.

Here's how the algorithm would work step-by-step:

Calculate the sum of the values of all nodes in the tree.
Calculate the sum of the values of all child nodes (i.e., the values of the nodes that are pointed to by other nodes).
Subtract the sum of the child node values from the sum of all node values. The result is the value of the root node.
Return the node whose value matches the remaining value. That node is the root.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def find_root(tree_nodes):
    all_nodes_sum = 0
    children_nodes_sum = 0

    # Calculate the sum of all nodes.
    for node in tree_nodes:
        all_nodes_sum += node.val

    # Calculate sum of all children nodes.
    for node in tree_nodes:
        for child in node.children:
            children_nodes_sum += child.val

    # The difference isolates the root node's value.
    root_value = all_nodes_sum - children_nodes_sum

    # Find the node with value equal to the difference.
    for node in tree_nodes:
        if node.val == root_value:
            root_node = node
            return root_node

    return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through all nodes in the tree once to calculate the sum of all node values, which takes O(n) time, where n is the number of nodes. Then, it iterates through all nodes again to calculate the sum of the values of the child nodes. Finally, it iterates through all nodes one last time to find the node whose value equals the difference. Thus, we have 3 iterations over n nodes which is O(3n), which simplifies to O(n).

Space Complexity

O(1) – The described solution calculates the sum of all node values and the sum of all child node values. It then finds the difference. The only extra space used is for a few variables to store these sums and the final root node value. The amount of extra memory used is independent of the number of nodes N in the tree; it uses the same amount of memory whether the tree has 10 nodes or 10,000 nodes. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty list of nodes	Return null/None, indicating an empty tree has no root.
Single node in the list	Return that single node as it is the root.
All nodes are the same object (same memory address)	The algorithm must not rely on node equality for comparison and should return the correct root node (if it exists).
Maximum number of nodes, potential memory issues	Ensure the solution uses memory efficiently and avoid creating unnecessary copies of the nodes.
The N-ary tree is disconnected, resulting in no root being identified	If no node has an indegree of zero, return null to indicate no single root exists.
Cycles exist within the N-ary tree structure	The indegree approach will still function properly as it's based on node references, not the paths.
Integer overflow in indegree calculations (if using integer counters)	Use a data type with sufficient range (e.g., long) to prevent overflow or use alternative approach that avoid indegree count.
Input list contains null nodes	Handle null nodes gracefully, skipping them in the processing to prevent NullPointerExceptions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree be empty (null or zero nodes)? What should be returned in that case?
What is the data type of the node's value and is there a range for these values?
Can nodes have a maximum number of children, or is the number of children unbounded?
Is the tree guaranteed to have a single root node, or is it possible to have disconnected components or no root at all?
Are the node objects distinct, or is it possible to have multiple nodes with the same value but different object identities?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by picking the first node in the list.
Go through all the other nodes to see if any of them point to our selected node as their child.
If no other node lists our selected node as a child, it might be the root, so we remember it.
Repeat these steps for every other node in the list.
After checking all the nodes, look at the ones we remembered as possible roots.
If we only have one possible root, then that's our answer. If we have multiple possible roots, then we can pick any of them since it means the input was invalid.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def find_root_brute_force(nodes):
    possible_roots = []

    for current_node in nodes:
        is_child = False
        for other_node in nodes:
            if current_node != other_node:
                if current_node in other_node.children:
                    is_child = True
                    break

        # Only add node to possible roots if no parent
        if not is_child:
            possible_roots.append(current_node)

    # Ensures that the edge cases work correctly
    if len(possible_roots) == 1:
        return possible_roots[0]
    elif len(possible_roots) > 0:
        return possible_roots[0]

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Calculate the sum of the values of all nodes in the tree.
Calculate the sum of the values of all child nodes (i.e., the values of the nodes that are pointed to by other nodes).
Subtract the sum of the child node values from the sum of all node values. The result is the value of the root node.
Return the node whose value matches the remaining value. That node is the root.

Code Implementation

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def find_root(tree_nodes):
    all_nodes_sum = 0
    children_nodes_sum = 0

    # Calculate the sum of all nodes.
    for node in tree_nodes:
        all_nodes_sum += node.val

    # Calculate sum of all children nodes.
    for node in tree_nodes:
        for child in node.children:
            children_nodes_sum += child.val

    # The difference isolates the root node's value.
    root_value = all_nodes_sum - children_nodes_sum

    # Find the node with value equal to the difference.
    for node in tree_nodes:
        if node.val == root_value:
            root_node = node
            return root_node

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty list of nodes	Return null/None, indicating an empty tree has no root.
Single node in the list	Return that single node as it is the root.
All nodes are the same object (same memory address)	The algorithm must not rely on node equality for comparison and should return the correct root node (if it exists).
Maximum number of nodes, potential memory issues	Ensure the solution uses memory efficiently and avoid creating unnecessary copies of the nodes.
The N-ary tree is disconnected, resulting in no root being identified	If no node has an indegree of zero, return null to indicate no single root exists.
Cycles exist within the N-ary tree structure	The indegree approach will still function properly as it's based on node references, not the paths.
Integer overflow in indegree calculations (if using integer counters)	Use a data type with sufficient range (e.g., long) to prevent overflow or use alternative approach that avoid indegree count.
Input list contains null nodes	Handle null nodes gracefully, skipping them in the processing to prevent NullPointerExceptions.