The longest path of unique node in a binary tree

Question

I've a question I struggle solving. I have an idea of solving but I think there is a more simple answer.
The question is:

Let's say there is a binary tree, which doesn't have to be complete or nearly complete.
There are n nodes in the tree and each contains a color out of k colors(k is a parameter). Find an algorithm that returns the longest simpale path in the tree where each node has unique color.
The path must go through the root(it doesn't have to start in the root).
Analyze the complexity of this algorithm.

My idea was to recursively go through every 2 groups of colors and find the longest unique path on each son that has only the group of colors that is matched to it. the problem is that it is complex to calculate the number of permutations you have to do. So I'm sure there is more "elegant" solution. Thanks a lot to everyone:)

Answer 1

As number of group of colors is $2^k$, your algorithm runs in exponential time. To get more precise bound, you need to be more specific about algorithm.

Anyway, there is much simpler way to do it: just take all pairs of nodes and check if they form valid path - that root is on path between them, and all nodes in the path have different colors. Naive implementation of it will require $O(n^3)$ operations ($O(n^2)$ pairs and $O(n)$ operations per pair).

The same idea can be improved to run in $O(n^2)$. Run DFS from the left child of root, keeping current depth and maintaining set of colors there on path from current node to root (add color when go to new node, and remove it when go up), without going to nodes with color already in set (as it will lead to having duplicate colors on path from this node to root already).

For each node in left subtree, run DFS on right subtree, again maintaining current depth and set of colors on path from the current node in left subtree to current node in right subtree.

Each operation in both DFS (going up or down) will take $O(1)$ time (check depth, add / remove node, etc.), and for at most $n$ nodes in left subtree we will run DFS on right subtree taking $O(n)$ time, so total time will be $O(n^2)$.