Univalued Binary Tree

Difficulty: Easy | Acceptance: 73.00% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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.

• Examples
• Constraints
• Recursive DFS
• Iterative DFS
• BFS

Examples

Input: root = [1,1,1,1,1,null,1]
Output: true

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

Recursive DFS

Intuition Traverse the tree recursively and check if each node’s value matches the root’s value.

Steps

• If current node is null, return true
• Check if left child exists and has different value than root
• Check if right child exists and has different value than root
• Recursively check left and right subtrees

# 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: Optional[TreeNode]) -> bool:
        if not root:
            return True
        if root.left and root.left.val != root.val:
            return False
        if root.right and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(h) where h is the height of the tree (recursion stack)
• Notes: Clean and intuitive, but may cause stack overflow for very deep trees

Iterative DFS

Intuition Use a stack to simulate recursion and traverse the tree iteratively while checking values.

Steps

• If root is null, return true
• Push root to stack and store root’s value
• While stack is not empty, pop a node
• If node’s value differs from root’s value, return false
• Push left and right children to stack if they exist

# 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: Optional[TreeNode]) -> bool:
        if not root:
            return True
        stack = [root]
        val = root.val
        while stack:
            node = stack.pop()
            if node.val != val:
                return False
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return True

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(n) in worst case for skewed tree
• Notes: Avoids recursion stack overflow, uses explicit stack

BFS

Intuition Traverse the tree level by level using a queue and check if all nodes have the same value.

Steps

• If root is null, return true
• Add root to queue and store root’s value
• While queue is not empty, dequeue a node
• If node’s value differs from root’s value, return false
• Enqueue left and right children if they exist

# 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
from collections import deque

class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        queue = deque([root])
        val = root.val
        while queue:
            node = queue.popleft()
            if node.val != val:
                return False
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return True

Complexity

• Time: O(n) where n is the number of nodes
• Space: O(w) where w is the maximum width of the tree
• Notes: Level-order traversal, useful when you need to process nodes by level