Code Implementation

# 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 countUnivalSubtrees(self, root: TreeNode) -> int:
        self.count = 0

        def is_unival(node):
            if not node:
                return True
            left_unival = is_unival(node.left)
            right_unival = is_unival(node.right)
            if not left_unival or not right_unival:
                return False
            if node.left and node.left.val != node.val:
                return False
            if node.right and node.right.val != node.val:
                return False
            self.count += 1
            return True

        is_unival(root)
        return self.count
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int count = 0;

    bool isUnival(TreeNode* node) {
        if (!node) return true;
        bool left = isUnival(node->left);
        bool right = isUnival(node->right);
        if (!left || !right)
            return false;
        if (node->left && node->left->val != node->val)
            return false;
        if (node->right && node->right->val != node->val)
            return false;
        count++;
        return true;
    }

    int countUnivalSubtrees(TreeNode* root) {
        count = 0;
        isUnival(root);
        return count;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int count = 0;

    public int countUnivalSubtrees(TreeNode root) {
        count = 0;
        isUnival(root);
        return count;
    }

    private boolean isUnival(TreeNode node) {
        if (node == null) return true;
        boolean left = isUnival(node.left);
        boolean right = isUnival(node.right);
        if (!left || !right) return false;
        if (node.left != null && node.left.val != node.val) return false;
        if (node.right != null && node.right.val != node.val) return false;
        count++;
        return true;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var countUnivalSubtrees = function(root) {
    let count = 0;
    function isUnival(node) {
        if (!node) return true;
        let left = isUnival(node.left);
        let right = isUnival(node.right);
        if (!left || !right) return false;
        if (node.left && node.left.val !== node.val) return false;
        if (node.right && node.right.val !== node.val) return false;
        count++;
        return true;
    }
    isUnival(root);
    return count;
};
      

Problem Description

You are given the root of a binary tree. Your task is to count the number of univalue subtrees within the tree. A univalue subtree is a subtree where all nodes have the same value.

Specifically, for each subtree (including leaves and the entire tree), check if every node in that subtree has the same value. If so, it is counted as a univalue subtree.

Constraints:

• The input is a binary tree defined by its root node, root.
• All node values are integers.
• The tree may be empty (in which case the answer is 0).

Thought Process

The first idea that comes to mind is to check every possible subtree in the tree and see if all its nodes have the same value. However, this brute-force approach would involve visiting each node multiple times, which is inefficient.

Instead, we can notice that:

• Every leaf node is a univalue subtree by itself.
• A parent node forms a univalue subtree with its children only if both subtrees are univalue and their values match the parent.

By thinking recursively, we can "bubble up" the univalue property from the leaves to the root, counting valid subtrees along the way and avoiding redundant checks.

Solution Approach

We use a recursive, post-order traversal to determine whether each subtree is univalue and to count them efficiently.

1. Base Case: If the current node is null, we return true because an empty subtree is trivially univalue.
2. Recursive Step: Recursively check if the left and right subtrees are univalue.
3. Value Check: If either subtree is not univalue, the current subtree can't be univalue.
4. Compare Values: If the left child exists and its value does not match the current node's value, return false. Do the same for the right child.
5. Count and Return: If all checks pass, increment the count and return true to indicate this subtree is univalue.

This approach ensures each node is visited only once, and each subtree is checked efficiently using information from its children.

Example Walkthrough

Consider the following binary tree:

        5
       / \
      1   5
     / \   \
    5   5   5
  

1. The leftmost leaf nodes (with value 5) are univalue subtrees (count = 1 for each).
2. The right child of the left subtree (also 5) is a univalue subtree (count = 1).
3. The left subtree rooted at 1 has children with value 5, so it is not univalue.
4. The right subtree rooted at 5 (with one right child 5) is univalue (count = 1 for the leaf, 1 for the parent).
5. The root node (5) has left subtree (not univalue) and right subtree (univalue with same value), but since left is not univalue, the whole tree is not univalue.
6. Total univalue subtrees: 4 leaves + 1 right subtree + 1 right child of root = 4

Time and Space Complexity

• Brute-force approach: For each node, traverse all its descendants to check if they are the same value. This can result in O(N^2) time complexity, where N is the number of nodes.
• Optimized recursive approach: Each node is visited once, and all checks are done in constant time per node. This results in O(N) time complexity.
• Space complexity: The recursion stack can be at most O(H), where H is the height of the tree. In the worst case (a skewed tree), H = N, but for balanced trees, H = log N.

Summary

By using a post-order traversal, we efficiently determine whether each subtree is univalue by leveraging information from its children. This avoids redundant work and ensures we only visit each node once. The key insight is that a subtree is univalue if both its children are univalue and their values match the current node. This recursive approach is both elegant and optimal for this problem, providing a clear and efficient solution.