Solution


Intuition and Algorithm

Let's output all the values of the array. After, we can check that they are all equal.

To output all the values of the array, we perform a depth-first search.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given tree.

  • Space Complexity: .


Approach 2: Recursion

Intuition and Algorithm

A tree is univalued if both its children are univalued, plus the root node has the same value as the child nodes.

We can write our function recursively. left_correct will represent that the left child is correct: ie., that it is univalued, and the root value is equal to the left child's value. right_correct will represent the same thing for the right child. We need both of these properties to be true.

Complexity Analysis

  • Time Complexity: , where is the number of nodes in the given tree.

  • Space Complexity: , where is the height of the given tree.


Analysis written by: @awice.