Problem

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

Example 1:

1
2
3
4
5
6
7
8

    1
   / \ 
  1   1
 / \   \ 
1  1    1

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

Example 2:

1
2
3
4
5
6
7

    2
   / \ 
  2   2
 / \ 
5   2
Input: root = [2,2,2,5,2]
Output: false

Solution

Method 1 - DFS

A binary tree is uni-valued if all of its nodes have the same value. To determine this, we need to traverse the binary tree and check whether the value of every node matches the value of the root node.

Approach

  1. Start from the root: Consider the value of the root node as the reference value.
  2. Traverse the tree: Use either a Depth First Search (DFS) or Breadth First Search (BFS) to visit all nodes in the tree.
  3. Comparison: Compare the value of each node with the reference value during traversal.
  4. Return result: If all nodes match the reference value, return true. Otherwise, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        def dfs(node: Optional[TreeNode], val: int) -> bool:
            if not node:
                return True
            if node.val != val:
                return False
            return dfs(node.left, val) and dfs(node.right, val)
        
        ref_val = root.val
        return dfs(root, ref_val)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        int refVal = root.val;

        return dfs(root, refVal);
    }

    private boolean dfs(TreeNode node, int val) {
        if (node == null) {
            return true;
        }
        if (node.val != val) {
            return false;
        }
        return dfs(node.left, val) && dfs(node.right, val);
    }
}

Complexity

  • ⏰ Time complexity: O(n). We need to visit each of the n nodes in the tree once.
  • 🧺 Space complexity: O(h). The space used by the traversal stack is proportional to the height h of the binary tree:
    • In the best case of a balanced binary tree, h = log(n).
    • In the worst case of a skewed binary tree, h = n.