Univalued Binary Tree

Problem Statement

In this problem, we are dealing with a binary tree where each node has an integer value. The challenge is to determine whether all nodes in the binary tree have the same value. This concept is termed "uni-valued". We are required to return true if every node in the tree shares the same value, and false otherwise. This verification needs to be made on any binary tree structure that could range from having only a single node to being a fully populated tree with varying depth and branching.

Examples

Example 1

Input:

root = [1,1,1,1,1,null,1]

Output:

true

Explanation:

All nodes in the tree have the value 1, so the tree is uni-valued.

Example 2

Input:

root = [2,2,2,5,2]

Output:

false

Explanation:

One of the nodes has value 5, while others have 2. Hence, the tree is not uni-valued.

Constraints

• The number of nodes in the tree is in the range [1, 100].
• 0 <= Node.val < 100

Approach and Intuition

1. Begin by examining the root. If the root is null, the tree is considered uni-valued as there are no values to compare.

2. If the root is not null, propagate through the tree using Depth-First Search (DFS) or Breadth-First Search (BFS) methods to compare the value of every node in the tree with the root’s value.

3. During the tree traversal:

   • If at any point a node does not match the value of the root, immediately return false.
   • Continue until all nodes have been compared. If no discrepancy in values is found, return true.

Why this works:

This simple traversal and comparison ensure the solution is efficient and works comfortably within the problem's constraints. Given the limit of 100 nodes and integer values between 0 and 99, either DFS or BFS will perform adequately.

Solutions

class Solution {
    public boolean checkUnivalTree(TreeNode root) {
        boolean left_same = (root.left == null ||
                (root.val == root.left.val && checkUnivalTree(root.left)));
        boolean right_same = (root.right == null ||
                (root.val == root.right.val && checkUnivalTree(root.right)));
        return left_same && right_same;
    }
}