Count Univalue Subtrees

Problem Statement

Given the root of a binary tree, the task is to determine the number of uni-value subtrees present within it. A uni-value subtree is one where every node within that subtree has the same value. This problem involves traversing the binary tree and validating each of its subtrees to see if they meet the criterion of having all nodes with identical values.

Examples

Example 1

Input:

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

Output:

4

Example 2

Input:

root = []

Output:

0

Example 3

Input:

root = [5,5,5,5,5,null,5]

Output:

6

Constraints

• The number of the node in the tree will be in the range [0, 1000].
• -1000 <= Node.val <= 1000

Approach and Intuition

To solve the problem of finding the number of uni-value subtrees in a binary tree, one can employ a depth-first search (DFS) algorithm. The key is to evaluate each subtree and count it if all its nodes share the same value. Here's how the approach can be broken down:

1. Initialize a counter to keep track of uni-value subtrees.
2. Create a recursive function that traverses the tree. For each node, compare its value to those of its children.
3. Specifically, for each node, ensure that:
   • If it has a left child, the left child's value should be the same as the current node's value.
   • Similarly, if it has a right child, the right child's value should match the current node's value.
4. If both conditions are satisfied (including conditions where a node might not have one or both children), then increment your uni-value subtree counter.
5. Return this count after the traversal of the tree is complete.

Intuitive Understanding

• Base Case of Emptiness: If the tree is empty (e.g., root = []), directly return 0 as there are no subtrees to evaluate.
• All Nodes Identical: In the case where all nodes have the same value (e.g., root = [5,5,5,5,5,null,5]), each subtree including the smallest ones (individual leaves) are uni-value. Here, even the whole tree is a uni-value subtree.
• Mixed Values: For trees with mixed values (e.g., root = [5,1,5,5,5,null,5]), we need to evaluate each potential subtree, leading to a possible mix of counts depending on subtree configurations and node values.

Through the DFS approach and checking each node in context with its children, the problem becomes manageable by breaking it down subtree by subtree, checking each for the uni-value condition.

Solutions

class Solution {
public:
    pair<bool, int> traverse(TreeNode* root) {
        if (!root) {
            return {true, 0};
        }
    
        auto leftResult = traverse(root->left);
        auto rightResult = traverse(root->right);
        bool isLeftUnival = leftResult.first;
        bool isRightUnival = rightResult.first;
        int totalUnivals = leftResult.second + rightResult.second;
    
        // Check if both left and right are unival subtrees and match current node's value
        if (isLeftUnival && isRightUnival) {
            if (root->left && root->val != root->left->val) {
                return {false, totalUnivals};
            }
            if (root->right && root->val != root->right->val) {
                return {false, totalUnivals};
            }
            return {true, totalUnivals + 1};
        }
    
        // If either left or right is not a unival subtree
        return {false, totalUnivals};
    }
    
    int countUnivalSubtrees(TreeNode* root) {
        return traverse(root).second;
    }
};