Find Root of a Colored Tree Python solution

In Python, create a set of all child ids while iterating over the edges, then return the node id not present in that set. Use a running sum of ids minus the child ids for an O(1) space version. Both run in O(n) time.

Is Find Root of a Colored Tree easy or hard?

This problem is rated Medium with a 41.9% acceptance rate. The core idea is simple once you see that the root never appears as a child, but many candidates struggle to reach the O(1) space solution without a hint.

How to solve Find Root of a Colored Tree in O(n)?

Read every edge and mark each child node. The root is the only node that is never marked. Use a hash set for clarity, or subtract each child id from the sum of all ids 1 to n to leave the root id with O(1) extra space.

What is the best approach for Find Root of a Colored Tree?

The best approach is a single pass over the edges that tracks which nodes appear as children. The sum difference method runs in O(n) time with O(1) extra space and is the most memory-efficient option. The hash set method is equally fast and easier to explain.

What data structure is used in Find Root of a Colored Tree?

The hash set approach uses a set to store child node ids for O(1) average lookup. The sum difference approach uses no data structure beyond a single integer accumulator. Both rely on the fact that the root is the only node with no parent.

What is the time complexity of Find Root of a Colored Tree?

The optimal solution runs in O(n) time, where n is the number of nodes, because it reads each edge once. The naive approach that scans the edge list for every candidate takes O(n²) time.

Is Find Root of a Colored Tree asked at Google, Amazon, or Meta?

This problem is not tagged with specific companies on FleetCode, so there is no confirmed company frequency data. The underlying pattern of identifying a root through in-degree or sum tricks appears frequently in tree interview questions across large tech companies.

Description Hints 6 Video 37:23

4085. Find Root of a Colored Tree

Medium41.9% acceptance

You are given an undirected tree of n nodes labeled from 0 to n - 1, represented by a 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that there is an undirected edge between nodes u_i and v_i.

You are also given a string colors of length n, where colors[i] is one of 'R', 'B', or 'W', and denotes the color of node i.

A node chosen as root must satisfy both of the following conditions once the tree is oriented away from it:

Binary-tree property: Every node has at most two children.
Layered color pattern: All nodes at the same depth have the same color. Starting at depth 0, these colors follow one of the three repeating sequences:
- R → B → W → R → B → W → ...
- B → W → R → B → W → R → ...
- W → R → B → W → R → B → ...

Return the index of any root that satisfies both conditions, or -1 if no such root exists.

A tree is a connected undirected graph with no cycles.

The depth of a node is the number of edges on the path from the root to that node. The root has depth 0. A child of a node is an adjacent node whose depth is one greater.

The degree of a node is the number of edges incident to it.

Example 1:

Input: edges = [[3,1],[3,2],[1,4],[2,0]], colors = "BRRWB"

Output: 3

Explanation:

Rooting at node 3 gives each node at most two children and every edge advances to the next color in the cycle (W → R → B), so return 3.

Example 2:

Input: edges = [[0,1],[1,2],[2,3]], colors = "RBRB"

Output: -1

Explanation:

No root satisfies the required color step on every edge, so return -1.

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i] = [u_i, v_i]
0 <= u_i, v_i < n
colors.length == n
colors[i] is one of 'R', 'B', 'W'.
The input graph is a tree and every node has degree at most three.

Hints open one at a time

Hint 1

1a (Forced Edge Orientations): Every parent-to-child edge must advance one step in the cycle R → B → W → R. Equal-colored endpoints make a solution impossible; otherwise, each edge has exactly one permitted direction.

Hint 2

1b (Forced Edge Orientations): A valid root must have indegree zero, and every other node must have indegree one. On a tree, these conditions ensure that all edges point away from the root.

Hint 3

1c (Forced Edge Orientations): The root must also have degree at most two. Every other node already has at most two children because its degree is at most three.

Hint 4

2a (Rerooting): Reject equal-colored edges. Root the tree arbitrarily and count edges whose child color is not the successor of the parent color.

Hint 5

2b (Rerooting): Moving the root across one edge reverses only that edge's parent-child direction. The number of incorrect edges increases by one if its old direction was correct, and decreases by one otherwise.

Hint 6

2c (Rerooting): Compute this count for every root in linear time. Return a node with no incorrect edges and degree at most two.

LanguageLoading editor…

1class Solution:
2    def findColoredRoot(self, edges: list[list[int]], colors: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[3,1],[3,2],[1,4],[2,0]]
"BRRWB"

Input

[[0,1],[1,2],[2,3]]
"RBRB"

Your code is saved on this device.