Univalued Binary Tree
We want to determine if a given binary tree is univalued, meaning that all nodes in the tree have the same value.
Approach
Define a Recursive Function: A simple way to solve this problem is by using a recursive function that traverses the tree and checks if all the nodes have the same value.
Check Node Values: In the recursive function, check if the current node’s value is the same as its parent’s value. If not, the tree is not univalued.
Traverse Left and Right Subtrees: Continue to traverse the left and right subtrees of the current node, performing the same check at each level.
Base Case: If the current node is
None
, return True as there are no values to compare in this branch.Final Result: The tree is univalued if all recursive calls return True.
Code


Example
 Input:
root = [1,1,1,1,1,null,1]
 Output:
true
 Explanation: All nodes have the value 1, so the tree is univalued.
Insights
Time Complexity: The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: The space complexity is (O(h)), where (h) is the height of the tree. This is the maximum amount of space required by the recursion stack.
Simple Recursive Solution: The solution demonstrates a simple use of recursion to traverse a binary tree and perform a comparison at each node.
 We have to visit all nodes
 It does not matter which traversal you use
 When you encounter a different value immediately return false
 Search for invariant
 Definition of the term univalued

