Univalued Binary Tree

Easy

#0919Time: 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).1 company

Algorithms

Depth-First Search Breadth-First Search

Data structures

Tree Binary Tree

Companies

Twilio

Prompt

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: true

Example 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 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.

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.

1import java.util.HashSet;2import java.util.Set;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public boolean isUnivalTree(TreeNode root) {21        if (root == null) {22            return true;23        }24        Set<Integer> values = new HashSet<>();25        collectValues(root, values);26        return values.size() == 1;27    }28 29    private void collectValues(TreeNode node, Set<Integer> values) {30        if (node == null) {31            return;32        }33        values.add(node.val);34        collectValues(node.left, values);35        collectValues(node.right, values);36    }37}

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.

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.

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.

Walkthrough

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.

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.
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.
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.
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.
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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean isUnivalTree(TreeNode root) {18        if (root == null) {19            return true;20        }21        return isUnival(root, root.val);22    }23 24    private boolean isUnival(TreeNode node, int value) {25        // Base case: An empty subtree is considered uni-valued.26        if (node == null) {27            return true;28        }29        // If the current node's value is different, the tree is not uni-valued.30        if (node.val != value) {31            return false;32        }33        // Recursively check the left and right subtrees.34        return isUnival(node.left, value) && isUnival(node.right, value);35    }36}

An iterative Breadth-First Search (BFS) using a queue is an alternative with similar performance characteristics.

Complexity

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).

Trade-offs

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.

Solutions

Solution

1/** * 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 ); } }

1/** * 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 ); } };

1# 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 )

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.

← Previous

Previous problem

Next problem