Univalued Binary Tree
DFS verifying every node's value matches the root's.
2 min read
tree dfs
Problem#
Return whether every node in the tree has the same value.
Examples#
[1,1,1,1,1,null,1]→true[2,2,2,5,2]→false
Constraints#
- The number of nodes is in
[1, 100].0 <= Node.val < 100.
Approach#
DFS comparing each node’s value against the root’s. Short-circuit on first mismatch.
Solution#
class Solution {public: bool isUnivalTree(TreeNode* root) { int v = root->val; function<bool(TreeNode*)> dfs = [&](TreeNode* u) { if (!u) return true; if (u->val != v) return false; return dfs(u->left) && dfs(u->right); }; return dfs(root); }};func isUnivalTree(root *TreeNode) bool { v := root.Val var dfs func(u *TreeNode) bool dfs = func(u *TreeNode) bool { if u == nil { return true } if u.Val != v { return false } return dfs(u.Left) && dfs(u.Right) } return dfs(root)}from typing import Optional
class Solution: def isUnivalTree(self, root: Optional[TreeNode]) -> bool: v = root.val
def dfs(u: Optional[TreeNode]) -> bool: if u is None: return True if u.val != v: return False return dfs(u.left) and dfs(u.right)
return dfs(root)function isUnivalTree(root) { const v = root.val; const dfs = (u) => { if (!u) return true; if (u.val !== v) return false; return dfs(u.left) && dfs(u.right); }; return dfs(root);}class Solution { private int v;
public boolean isUnivalTree(TreeNode root) { v = root.val; return dfs(root); }
private boolean dfs(TreeNode u) { if (u == null) return true; if (u.val != v) return false; return dfs(u.left) && dfs(u.right); }}function isUnivalTree(root: TreeNode | null): boolean { if (!root) return true; const v = root.val; const dfs = (u: TreeNode | null): boolean => { if (!u) return true; if (u.val !== v) return false; return dfs(u.left) && dfs(u.right); }; return dfs(root);}Editorial#
Comparing against the root rather than the parent is equivalent (transitivity), and avoids passing extra state. The early return on mismatch keeps the walk short for negative inputs.
Complexity#
- Time: O(n).
- Space: O(h).
Concept revision#
Related#