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:
[1, 100].0 <= Node.val < 100Problem Overview: You are given the root of a binary tree. The task is to determine whether every node in the tree contains the same value. If all nodes share the identical value, the tree is considered univalued. Return true if the tree satisfies this property, otherwise return false.
Since the constraint involves checking every node's value against a single reference value, the core idea is simple: traverse the tree and verify that no node deviates from the root value. Tree traversal techniques such as Depth-First Search and Breadth-First Search work well because they visit every node exactly once.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
Recursive DFS walks through the tree while comparing each node's value with the root's value. Start by storing root.val. Recursively check the left and right children. If a node is null, treat it as valid and return true. If a node’s value differs from the reference value, immediately return false. Otherwise, recursively validate both subtrees. The recursion stack uses O(h) space where h is the height of the tree, which becomes O(n) in the worst case of a skewed tree and O(log n) for balanced trees.
This approach is concise and maps naturally to the recursive structure of a binary tree. Each node is processed once, so the total runtime remains linear.
Approach 2: Iterative Breadth-First Search (BFS) (Time: O(n), Space: O(n))
Iterative BFS uses a queue to traverse the tree level by level. Push the root node into the queue and store its value as the reference. While the queue is not empty, remove the front node and compare its value to the reference. If the values differ, return false. Otherwise, push the node’s left and right children into the queue if they exist.
This method ensures every node is visited exactly once. The queue may temporarily store up to an entire level of the tree, which results in O(n) space in the worst case. BFS is useful if you prefer iterative logic or want explicit control over traversal without recursion.
Recommended for interviews: Recursive DFS is typically the expected solution because it is short, readable, and directly follows the recursive nature of trees. Implementing DFS shows strong understanding of tree traversal and recursion. BFS is equally correct and demonstrates familiarity with queue-based traversal, which interviewers also value when discussing alternatives.
The recursive DFS approach involves starting from the root and checking if every node has the same value as the root node. This can be achieved by recursively checking the left and right subtrees of each node. If a node value differs from the root node's value, we return false immediately.
The function isUnival() checks recursively whether the node value equals the desired value (root->val). This involves checking the left and right subtrees. If any node value doesn't match, it returns false.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
An iterative BFS approach uses a queue to level-order traverse the tree. We compare each node's value to the root's value. If any node differs, the function returns false.
This C solution uses an explicit queue structure to iteratively traverse nodes level-wise, checking if each has the same value as the root. Queues ensure that nodes are processed in insertion order.
Time Complexity: O(n), as each node is checked once.
Space Complexity: O(n), due to the queue storing at most one level of the tree.
We denote the value of the root node as x, and then design a function dfs(root), which indicates whether the current node's value is equal to x and its left and right subtrees are also univalued binary trees.
In the function dfs(root), if the current node is null, return true; otherwise, if the current node's value is equal to x and its left and right subtrees are also univalued binary trees, return true; otherwise, return false.
In the main function, we call dfs(root) and return the result.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once. |
| Iterative Breadth-First Search (BFS) | Time Complexity: O(n), as each node is checked once. |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best default approach for binary trees. Clean recursive logic and minimal code. |
| Iterative Breadth-First Search (BFS) | O(n) | O(n) | Useful when recursion depth may be large or when practicing queue-based tree traversal. |
Univalued Binary Tree || Leetcode 965 • Code with Newton • 1,094 views views
Watch 9 more video solutions →Practice Univalued Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor