Univalued Binary Tree
EasyPrompt
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:
Input: root = [1,1,1,1,1,null,1]
Output: trueExample 2:
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
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- If the
rootis null, returntrue. - Create an empty
HashSetto 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
rootnode. - After the traversal is complete, check the size of the set.
- Return
trueif the size is 1, otherwise returnfalse.
Walkthrough
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.
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); }}Complexity
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).
Trade-offs
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.
Solutions
Solution
/** * 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 ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.