Univalued Binary Tree — Solution in Python, Java & C++
Univalued Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon.
Univalued Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A binary tree is uni-valued if every node in it holds the same value.
Given the root of a binary tree, return true if the tree is uni-valued, and false otherwise.
Example 1
Input: root = [1,1,1,1,1,null,1]
Output: true
Explanation: Every node holds 1.
Example 2
Input: root = [2,2,2,5,2]
Output: false
Explanation: One node holds 5.
Example 3
Input: root = [7]
Output: true
Explanation: A single node is trivially uni-valued.
Constraints
1 <= number of nodes <= 1000 <= Node.val < 100
Hints for Univalued Binary Tree
Hint 1
If the tree is uni-valued, the shared value must be the root's.
Hint 2
Visit every node and compare it with the root's value.
Hint 3
Stop at the first node that differs — one mismatch is enough to answer
false.
How to solve Univalued Binary Tree
The only candidate for the common value is the root's value, so the question becomes: does any node differ from the root?
Approach
- Remember
v = root.val. - Traverse the tree (depth-first with a stack, or breadth-first with a queue).
- If a node's value is not
v, returnfalseimmediately. - If the traversal finishes, return
true.
Complexity
- Time —
O(n) - Space —
O(h) for a depth-first stack
Pitfalls
- Comparing each node only with its parent also works, but comparing everything with one fixed value is simpler and just as fast.
Reference solution
Python
from typing import Optional
def isUnivalTree(root: Optional[TreeNode]) -> bool:
v = root.val
stack = [root]
while stack:
node = stack.pop()
if node.val != v:
return False
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return TrueJava
public static boolean isUnivalTree(TreeNode root) {
return same(root, root.val);
}
static boolean same(TreeNode node, int v) {
if (node == null) return true;
return node.val == v && same(node.left, v) && same(node.right, v);
}C++
bool sameValue(TreeNode* node, int v);
bool isUnivalTree(TreeNode* root) {
return sameValue(root, root->val);
}
bool sameValue(TreeNode* node, int v) {
if (!node) return true;
return node->val == v && sameValue(node->left, v) && sameValue(node->right, v);
}JavaScript
var isUnivalTree = function(root) {
var v = root.val, stack = [root];
while (stack.length > 0) {
var node = stack.pop();
if (node.val !== v) return false;
if (node.left !== null) stack.push(node.left);
if (node.right !== null) stack.push(node.right);
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)