250. Count Univalue Subtrees

MediumTreeDepth-First SearchBinary Tree
Leetcode Link

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.

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:

  1. 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.

  2. We call the recursive function on the left and right child of the current node.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

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:

  1. 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.

  2. 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.

  3. Recursive Calls: We store the results of the dfs calls on the left and right subtrees in the l and r variables, respectively.

  4. 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.

  5. 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.

  6. 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.

  7. Return Value for Uni-value Subtrees: After incrementing the ans variable for a uni-value subtree, the dfs function returns True.

  8. Return Value for Non-Uni-value Subtrees: If the subtree rooted at root is not uni-value, then the function returns False.

  9. 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.

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

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

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

1    1
2   / \
3  1   1
4 /   / \
51   1   1

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:

  1. We start the depth-first search (DFS) traversal by calling the dfs function on the root node (value 1).

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Tree Min Depth

Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ