# Univalued Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/univalued-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/univalued-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Twilio](https://scaleengineer.com/companies/twilio)
---
## Problem
A binary tree is **uni-valued** if every node in the tree has the same value.

Given the `root` of a binary tree, return `true` _if the given tree is **uni-valued**, or_ `false` _otherwise._

**Example 1:**

![](https://assets.glich.co/dsa/univalued-binary-tree/image0.png) 

**Input:** root = [1,1,1,1,1,null,1]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/univalued-binary-tree/image1.png) 

**Input:** root = [2,2,2,5,2]
**Output:** false

**Constraints:**

* The number of nodes in the tree is in the range `[1, 100]`.
* `0 <= Node.val < 100`

# Approaches
## Brute Force: Traversal and Store
This approach involves traversing the entire tree and storing the value of each node. After the traversal, we check if only one unique value was found.
**Time:** O(N), where N is the number of nodes in the tree. This is because we must visit every single node to populate the set. · **Space:** O(N) in the worst case. The `HashSet` can store up to N unique values if all nodes have different values. Additionally, the recursion stack for the traversal will use O(H) space, where H is the height of the tree. For a skewed tree, H can be N, making the total space complexity O(N).
**Pros:** The logic is straightforward and easy to understand.
**Cons:** Inefficient in terms of time, as it always traverses the entire tree, failing to exit early even when a non-matching value is found.; Uses extra space (up to O(N)) for the `HashSet`, which is not necessary for solving the problem.
### Explanation
This method involves a full tree traversal (e.g., pre-order DFS) to visit every node. During the traversal, each node's value is added to a `HashSet`. The `HashSet` efficiently stores only the unique values encountered.

Once the entire tree has been visited, we check the final size of the `HashSet`. If the size is 1, it confirms that all nodes share the same value, and the tree is uni-valued. If the size is greater than 1, multiple distinct values were found, and the tree is not uni-valued.

This approach is straightforward but inefficient because it always traverses the whole tree and uses extra space for the set, failing to stop early if a mismatch is found.

```java
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Set<Integer> values = new HashSet<>();
        collectValues(root, values);
        return values.size() == 1;
    }

    private void collectValues(TreeNode node, Set<Integer> values) {
        if (node == null) {
            return;
        }
        values.add(node.val);
        collectValues(node.left, values);
        collectValues(node.right, values);
    }
}
```
### Algorithm
- If the `root` is null, return `true`.
- Create an empty `HashSet` to store the unique node values.
- Define a recursive traversal function that takes a node and the set as arguments.
- In the traversal function, if the node is not null, add its value to the set and then recursively call the function for its left and right children.
- Start the traversal from the `root` node.
- After the traversal is complete, check the size of the set.
- Return `true` if the size is 1, otherwise return `false`.

## Optimal Traversal with Early Exit (DFS)
A more efficient approach is to traverse the tree while comparing each node's value with an expected value (the root's value). If we find any node with a different value, we can immediately conclude the tree is not uni-valued and stop the traversal.
**Time:** O(N), where N is the number of nodes. In the worst case, if the tree is uni-valued, we must visit every node once. However, in the best case (e.g., the root's child has a different value), the algorithm can terminate in O(1) time. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. For a balanced tree, H is O(log N). For a skewed tree, H can be O(N).
**Pros:** Highly efficient, as it stops processing and returns `false` as soon as a non-matching node is found.; Optimal time complexity for this problem.; Space-efficient, especially for balanced trees.
**Cons:** A recursive solution might lead to a `StackOverflowError` for extremely deep trees, although this is not a concern given the problem's constraint of at most 100 nodes.
### Explanation
This optimal approach is based on the definition of a uni-valued tree: all nodes must have the same value. This value must, therefore, be the same as the root node's value. We can leverage this fact for an efficient check.

We can use a Depth-First Search (DFS) traversal, which is naturally implemented with recursion.
1.  First, we check if the tree is empty. An empty tree can be considered uni-valued. If not empty, we record the value of the `root` node. This value is our benchmark for all other nodes.
2.  We then define a recursive helper function, say `dfs(node, value)`, which returns `true` if the subtree at `node` is uni-valued with the given `value`, and `false` otherwise.
3.  The base case for the recursion is when a node is `null`. A null node does not violate the uni-valued property, so we return `true`.
4.  For a non-null node, we first check if its value (`node.val`) is equal to the target `value`. If it's not, we have found a discrepancy. The tree is not uni-valued, so we immediately return `false`. This allows for an early exit, which is a key advantage over the brute-force method.
5.  If the current node's value matches, we must ensure the same holds for its entire left and right subtrees. We do this by making recursive calls: `dfs(node.left, value)` and `dfs(node.right, value)`. The current subtree is uni-valued only if both of these calls return `true`.

This approach is significantly more efficient as it terminates as soon as the first mismatch is found.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isUnival(root, root.val);
    }

    private boolean isUnival(TreeNode node, int value) {
        // Base case: An empty subtree is considered uni-valued.
        if (node == null) {
            return true;
        }
        // If the current node's value is different, the tree is not uni-valued.
        if (node.val != value) {
            return false;
        }
        // Recursively check the left and right subtrees.
        return isUnival(node.left, value) && isUnival(node.right, value);
    }
}
```
An iterative Breadth-First Search (BFS) using a queue is an alternative with similar performance characteristics.
### Algorithm
- If the `root` node is `null`, return `true`.
- Store the value of the `root` node in a variable, `val`.
- Define a recursive helper function `isUnival(node, val)`.
- **Base Case:** Inside the helper, if `node` is `null`, return `true`.
- **Check:** Check if `node.val` is equal to `val`. If not, return `false` immediately.
- **Recurse:** Return the result of `isUnival(node.left, val) AND isUnival(node.right, val)`.
- Call the helper function with the `root` and `val` and return its result.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isUnivalTree ( TreeNode root ) { return dfs ( root , root . val ); } private boolean dfs ( TreeNode root , int val ) { if ( root == null ) { return true ; } return root . val == val && dfs ( root . left , val ) && dfs ( root . right , val ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isUnivalTree ( TreeNode * root ) { return dfs ( root , root -> val ); } bool dfs ( TreeNode * root , int val ) { if ( ! root ) return true ; return root -> val == val && dfs ( root -> left , val ) && dfs ( root -> right , val ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isUnivalTree ( self , root : TreeNode ) -> bool : def dfs ( node ): if node is None : return True return node . val == root . val and dfs ( node . left ) and dfs ( node . right ) return dfs ( root )
```