250. Count Univalue Subtrees

Problem Description

The task is to determine the number of subtrees within a binary tree where all nodes have the same value. These subtrees, where all nodes share a common value, are referred to as uni-value subtrees. The input is the root of the binary tree, and the expected output is an integer representing the total count of uni-value subtrees within that tree.

Flowchart Walkthrough

Let's analyze the LeetCode problem "250. Count Univalue Subtrees" using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: We can interpret the input tree structure as a graph where nodes are tree nodes and edges are the connections between them.

Is it a tree?

Yes: The data structure provided is directly a tree, as specified in the problem (it explicitly involves counting something specific in a tree structure).

DFS

Since we've determined that the structure is a tree, Depth-First Search (DFS) is an appropriate algorithmic pattern. DFS can efficiently traverse each node to check the univalue subtree property.

Conclusion: Using Depth-First Search (DFS) in a tree is typical for problems involving recursive checking of properties for each node or subtree, such as determining if all nodes in a subtree have the same value. This type of traversal is ideal for "Count Univalue Subtrees" since we need to traverse each node and its subtrees to verify and count the number of univalue subtrees.

Thus, the flowchart directly leads to using DFS for this problem, as this method allows for an effective recursive analysis of each subtree in the context of its parent and children to check constancy of values.

Intuition

To solve the problem, we can use recursion. A recursive function can traverse the tree while keeping track of uni-value subtrees. Here's the general idea:

If the current node is None (meaning we've reached a leaf node's child), we return True because a non-existent node doesn't disrupt a subtree's uni-value status.
We call the recursive function on the left and right child of the current node.
If any child subtree is not uni-value (the recursive call returns False), then the current subtree also cannot be uni-value. Hence, we return False immediately.
Otherwise, we need to check if the current node's value matches the values of its children (if they exist). If the current node is a leaf or if it has children with the same value as itself, then it's a root of a uni-value subtree.
We use a nonlocal variable ans to maintain the count of uni-value subtrees found during the traversal. This variable is incremented each time we find such a subtree.
Finally, we return True or False from the recursive function to indicate whether the subtree rooted at the current node is a uni-value subtree.

The solution leverages a depth-first search (DFS) approach, processing each node and its subtrees to determine uni-value status. By starting from the leaves and working up to the root, we effectively employ a bottom-up approach. This way, we ensure that a node is counted only when all its descendants form uni-value subtrees.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The implementation of the solution involves defining a nested helper function dfs(root) inside the countUnivalSubtrees method of a Solution class. This recursive function is the core of the depth-first search (DFS) strategy. Below is a detailed walk-through of the code:

Recursive Depth-First Search (DFS): The dfs function is recursively called on both the left and right children of a node. This traversal goes down to the leaf nodes of the binary tree.
Base Case: When the root is None, we've reached beyond the leaf nodes, and in this case, the function returns True because a non-existent node doesn't affect the uni-value property of a subtree.
Recursive Calls: We store the results of the dfs calls on the left and right subtrees in the l and r variables, respectively.
Early Return: If either l or r is False, it means that at least one of the subtrees (left or right) isn't uni-value, and thus, the current subtree rooted at root can't be uni-value either. So the function returns False immediately.
Comparison with Children's Values: The current node's value is compared with its children's values. If there is no left or right child, the value of root is used for comparison to ensure that a leaf node is always considered a uni-value subtree. If both comparisons result in equality (a == b == root.val), then the current subtree is uni-value.
Counting Uni-value Subtrees: When a uni-value subtree is identified, we increment the ans variable. Here, nonlocal ans is used to modify the ans variable defined in the enclosing countUnivalSubtrees function, effectively keeping track of the total count.
Return Value for Uni-value Subtrees: After incrementing the ans variable for a uni-value subtree, the dfs function returns True.
Return Value for Non-Uni-value Subtrees: If the subtree rooted at root is not uni-value, then the function returns False.
Answer Retrieval: After calling dfs(root), countUnivalSubtrees returns the final count of uni-value subtrees stored in ans.

The solution overall uses a bottom-up DFS approach to check for the uni-value property on each subtree starting from the leaves and moving to the root. A TreeNode class represents the nodes of the tree, encapsulating the value of the node and pointers to left and right children. This DFS allows us to ensure that every node is counted exactly once and only as part of the largest possible uni-value subtree that it's a root of.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple binary tree to illustrate the solution approach:

In this example binary tree, all nodes have the same value: 1. We want to count the number of uni-value subtrees in this tree.

Here's how the solution approach would work on this tree:

We start the depth-first search (DFS) traversal by calling the dfs function on the root node (value 1).
The DFS goes down to the left-most node first, which is another 1. Since it's a leaf, the base case makes the function return True.
As the recursion unwinds, we check this node’s parent, which is also 1. Both the left and right children are either None or have the same value. So this subtree is also a uni-value subtree. ans is incremented.
We move up the tree, and now the parent is the root. The same logic applies: since both its children are univalues (True from the recursive calls), and their values match the root’s value (1), we consider the whole tree as a uni-value subtree, and ans is incremented again.
Now, we move to the right subtree. Since we recursively find that both the right child and the left child (both with value 1) are uni-value subtrees, they result in two more increments of ans.
Finally, we finish the traversal. As all the nodes and their subtrees have been evaluated as uni-value, the ans reflects the total number of uni-value subtrees. In this case, ans would be 5 since there are five nodes and each node itself can be considered a subtree, providing they all have the same value.
The countUnivalSubtrees function will then return ans as the final count of uni-value subtrees, which is 5 for our example.

Thus, by processing each node and its subtrees in a bottom-up DFS manner, we effectively count all subtrees in the binary tree where all nodes have the same value.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def countUnivalSubtrees(self, root: Optional[TreeNode]) -> int:
10        # Helper function to perform depth-first search
11        def is_unival_subtree(node):
12            # Base case: An empty tree is a unival tree by default
13            if node is None:
14                return True
15          
16            # Recursively check if left and right subtrees are unival
17            is_left_unival = is_unival_subtree(node.left)
18            is_right_unival = is_unival_subtree(node.right)
19          
20            # If either left or right subtree is not unival, return False
21            if not is_left_unival or not is_right_unival:
22                return False
23          
24            # Get the value of the left child, or use the current node's value if left child is None
25            left_val = node.val if node.left is None else node.left.val
26            # Get the value of the right child, or use the current node's value if right child is None
27            right_val = node.val if node.right is None else node.right.val
28          
29            # Check if current node is unival, which means its value equals to
30            # both its children's value (or it doesn't have children)
31            if left_val == right_val == node.val:
32                # Increment the count as this is a unival subtree
33                nonlocal total_unival_subtrees
34                total_unival_subtrees += 1
35                return True
36          
37            # If the current node's value does not match one or both of its children's
38            # values, this subtree cannot be unival
39            return False
40
41        # Start with no unival subtrees counted
42        total_unival_subtrees = 0
43      
44        # Kick off the depth-first search from the root
45        is_unival_subtree(root)
46      
47        # Return the total count of unival subtrees
48        return total_unival_subtrees
49

1class Solution {
2    private int univalSubtreeCount;
3
4    public int countUnivalSubtrees(TreeNode root) {
5        // Performs DFS traversal to count unival subtrees
6        dfs(root);
7        return univalSubtreeCount;
8    }
9
10    private boolean dfs(TreeNode node) {
11        // If current node is null, it is a unival subtree.
12        if (node == null) {
13            return true;
14        }
15        // Recursively check if the left subtree is unival
16        boolean isLeftUnival = dfs(node.left);
17        // Recursively check if the right subtree is unival
18        boolean isRightUnival = dfs(node.right);
19      
20        // If either left or right subtree is not unival, return false
21        if (!isLeftUnival || !isRightUnival) {
22            return false;
23        }
24
25        // Capture the values of left and right children. 
26        // Use the current node's value if the child is null.
27        int leftVal = node.left == null ? node.val : node.left.val;
28        int rightVal = node.right == null ? node.val : node.right.val;
29
30        // If the left value equals right value and also equals the current node value, 
31        // it's a unival subtree, increment the count.
32        if (leftVal == rightVal && rightVal == node.val) {
33            univalSubtreeCount++;
34            return true;
35        }
36
37        // Otherwise, the subtree rooted at the current node isn't unival
38        return false;
39    }
40}
41

1class Solution {
2public:
3    // Helper method to count unival subtrees.
4    int countUnivalSubtrees(TreeNode* root) {
5        int ans = 0; // Counter for the number of unival subtrees.
6      
7        // Inner function to perform a depth-first search.
8        std::function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
9            if (!node) {
10                return true; // An empty tree is a unival subtree.
11            }
12          
13            // Recursively check if left and right subtrees are unival.
14            bool isLeftUnival = dfs(node->left);
15            bool isRightUnival = dfs(node->right);
16          
17            // If either of the subtrees is not unival, the current tree can't be unival.
18            if (!isLeftUnival || !isRightUnival) {
19                return false;
20            }
21          
22            // Check if the current node is unival with its children.
23            int leftVal = node->left ? node->left->val : node->val;
24            int rightVal = node->right ? node->right->val : node->val;
25          
26            if (leftVal == rightVal && rightVal == node->val) {
27                // If the current node and its children have the same value, it is a unival subtree.
28                ++ans;
29                return true;
30            }
31          
32            return false; // Current subtree is not unival as the node values differ.
33        };
34      
35        dfs(root); // Start DFS from the root.
36        return ans; // Return the total number of unival subtrees found.
37    }
38};
39
40/**
41 * Definition for a binary tree node.
42 * struct TreeNode {
43 *     int val; // Value of the node.
44 *     TreeNode *left; // Pointer to the left child.
45 *     TreeNode *right; // Pointer to the right child.
46 *     // Constructor for a node with default value 0 and no children
47 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
48 *     // Constructor for a node with given value x and no children
49 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
50 *     // Constructor for a node with given value x and given children
51 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
52 * };
53 */
54

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6  
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = (val === undefined ? 0 : val);
9        this.left = (left === undefined ? null : left);
10        this.right = (right === undefined ? null : right);
11    }
12}
13
14// Counts the number of universal value subtrees within the binary tree.
15// A subtree is considered universal if all nodes within the subtree have the same value.
16function countUnivalSubtrees(root: TreeNode | null): number {
17    let count: number = 0;
18
19    // Helper function to perform depth-first search.
20    // Returns true if the subtree rooted at the given node is universal.
21    const isUnivalSubtree = (node: TreeNode | null): boolean => {
22        if (node == null) {
23            // A null node is considered a universal subtree.
24            return true;
25        }
26
27        // Recursively check the left and right subtrees.
28        const isLeftUnival: boolean = isUnivalSubtree(node.left);
29        const isRightUnival: boolean = isUnivalSubtree(node.right);
30
31        // If either subtree is not universal, then this cannot be a universal subtree.
32        if (!isLeftUnival || !isRightUnival) {
33            return false;
34        }
35
36        // If left child exists and its value is not equal to current node's value, this is not a universal subtree.
37        if (node.left != null && node.left.val != node.val) {
38            return false;
39        }
40
41        // If right child exists and its value is not equal to current node's value, this is not a universal subtree.
42        if (node.right != null && node.right.val != node.val) {
43            return false;
44        }
45
46        // Current subtree is universal; increment count and return true.
47        count++;
48        return true;
49    };
50
51    // Kick-off the depth-first search from the root.
52    isUnivalSubtree(root);
53
54    // Return the final count of universal subtrees.
55    return count;
56}
57

Time and Space Complexity

The given Python function counts the number of "unival" (universal value) subtrees within a binary tree, where a unival subtree is one that has all nodes with the same value.

Time Complexity:

To determine the time complexity, let's consider the action performed by the function and how often it's executed. The solution uses a depth-first search (DFS) strategy, exploring the tree from root to leaves. For each node, it performs a constant number of operations – checking the value of the node, comparing it with its children, and updating the answer variable if it forms a unival subtree.

The DFS traverses each node exactly once since it follows the standard recursion pattern without revisiting any node. Since there are n nodes in the tree, the traversal results in O(n) operations where n is the number of nodes in the binary tree.

Thus, the Time Complexity is O(n).

Space Complexity:

The recursive solution also incurs space complexity due to the use of the recursion stack. In the worst case, where the binary tree is skewed (each parent has only one child), the recursion goes as deep as the number of nodes, leading to the maximum depth of recursion stack being n. Therefore, the Space Complexity in the worst case is O(n).

However, in the best case where the tree is perfectly balanced, the height of the tree would be log(n). Thus, the space complexity would be O(log(n)). But since worst-case scenario often dictates our space complexity analysis, we generally consider the former scenario for evaluation.

In summary, the Space Complexity is O(n) in the worst case, with the best case being O(log(n)) if the tree is balanced.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know