FastPrepFind the Root of a Directed Tree
Problem · Tree

Find the Root of a Directed Tree

Learn this problem
● EasyAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given every node identifier in a rooted tree and directed edges [parent, child]. Return the unique root identifier.

For this exercise, assume node identifiers are unique nonnegative integers, every non-root node appears as a child exactly once, and the input always describes one valid rooted tree. A single-node tree has no edges.

Function

findTreeRoot(nodes: int[], edges: int[][]) → int

Examples

Example 1

nodes = [4,7,9,12]edges = [[7,4],[7,9],[9,12]]return = 7

Every node except 7 appears as a child, so 7 is the root.

Example 2

nodes = [42]edges = []return = 42

The only node is the root.

Constraints

  • 1 <= nodes.length <= 10^5
  • edges.length = nodes.length - 1
  • The input describes one valid rooted tree.

More Amazon problems

drafts saved locally
public int findTreeRoot(int[] nodes, int[][] edges) {
    // Your code here
}
nodes[4,7,9,12]
edges[[7,4],[7,9],[9,12]]
expected7
checking account