Solution
Approach 1: DepthFirst Search
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 depthfirst 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.