Count Univalue Subtrees solution and explanation
Google
9 more videos on this problem
LEETCODE 250 (JAVASCRIPT) | COUNT UNIVALUE SUBTREESAndy Gala · 10:13 · 2K views
Count univalue Subtrees - Google Interview QuestionAlgorithms Casts · 24:35 · 2K views
LeetCode 250: Count Univalue SubtreesKevin Dai · 3:59 · 942 views
250. Count Univalue Subtrees - Week 5/5 Leetcode June ChallengeProgramming Live with Larry · 6:43 · 686 views
LeetCode 250 Count Univalue SubtreesLeonZ · 8:18 · 462 views
Count Univalue Subtrees - LeetCode 250 - PythonAlpha-Code · 11:06 · 454 views
Leetcode Problem 250 - Count Univalued Subtrees: March 26th, 2021Remy B99 · 11:43 · 261 views
250. Count Univalue Subtrees (C++)Gilbert Zhuo · 5:13 · 133 views
leetcode 250. Count Univalue Subtrees - recursionCode-Yao · 15:03 · 128 views
COUNT UNIVALUE SUBTREES | LEETCODE 250 | MEDIUM | PYTHONAniPy · 12:10 · 99 views
The problem
Given the root of a binary tree, return the number of uni-value subtrees.
A uni-value subtree means all nodes of the subtree have the same value.
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 overview
Problem Overview: Given a binary tree, count how many subtrees are univalue. A subtree is univalue if every node inside it has the same value. Each node can be the root of its own subtree, so you must verify whether all nodes below it match.
Approach 1: Brute Force Subtree Validation (O(n^2) time, O(h) space)
Traverse every node and treat it as the root of a potential univalue subtree. For each node, run a helper DFS that checks whether all nodes in that subtree match the root value. This repeatedly scans the same nodes when validating overlapping subtrees, which leads to O(n^2) time in the worst case for skewed trees. Space complexity is O(h) due to recursion depth, where h is the tree height. This approach is straightforward but inefficient because subtree validation is recomputed many times.
Approach 2: Postorder DFS with State Propagation (O(n) time, O(h) space)
Traverse the tree using postorder DFS so children are processed before their parent. Each recursive call returns whether the current subtree is univalue. A node forms a univalue subtree if its left and right subtrees are univalue and their values (if they exist) match the current node's value. When this condition holds, increment a global counter and return true to the parent. Every node is visited exactly once, giving O(n) time complexity with O(h) recursion stack space. This approach avoids repeated subtree scans by propagating validity information upward.
The algorithm relies on standard traversal patterns from depth-first search applied to a binary tree. Postorder traversal is key because a node's validity depends on the results from both children.
Recommended for interviews: The postorder DFS approach is what interviewers expect. It demonstrates that you can propagate state during recursion and avoid redundant work. Mentioning the brute force method first shows understanding of the problem space, but implementing the O(n) DFS solution proves stronger algorithmic thinking when working with tree structures.
Solution
# 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: Optional[TreeNode]) -> int:
def dfs(root):
if root is None:
return True
l, r = dfs(root.left), dfs(root.right)
if not l or not r:
return False
a = root.val if root.left is None else root.left.val
b = root.val if root.right is None else root.right.val
if a == b == root.val:
nonlocal ans
ans += 1
return True
return False
ans = 0
dfs(root)
return ans/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int countUnivalSubtrees(TreeNode root) {
dfs(root);
return ans;
}
private boolean dfs(TreeNode root) {
if (root == null) {
return true;
}
boolean l = dfs(root.left);
boolean r = dfs(root.right);
if (!l || !r) {
return false;
}
int a = root.left == null ? root.val : root.left.val;
int b = root.right == null ? root.val : root.right.val;
if (a == b && b == root.val) {
++ans;
return true;
}
return false;
}
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countUnivalSubtrees(TreeNode* root) {
int ans = 0;
function<bool(TreeNode*)> dfs = [&](TreeNode* root) -> bool {
if (!root) {
return true;
}
bool l = dfs(root->left);
bool r = dfs(root->right);
if (!l || !r) {
return false;
}
int a = root->left ? root->left->val : root->val;
int b = root->right ? root->right->val : root->val;
if (a == b && b == root->val) {
++ans;
return true;
}
return false;
};
dfs(root);
return ans;
}
};/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countUnivalSubtrees = function (root) {
let ans = 0;
const dfs = root => {
if (!root) {
return true;
}
const l = dfs(root.left);
const r = dfs(root.right);
if (!l || !r) {
return false;
}
if (root.left && root.left.val !== root.val) {
return false;
}
if (root.right && root.right.val !== root.val) {
return false;
}
++ans;
return true;
};
dfs(root);
return ans;
};/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function countUnivalSubtrees(root: TreeNode | null): number {
let ans: number = 0;
const dfs = (root: TreeNode | null): boolean => {
if (root == null) {
return true;
}
const l: boolean = dfs(root.left);
const r: boolean = dfs(root.right);
if (!l || !r) {
return false;
}
if (root.left != null && root.left.val != root.val) {
return false;
}
if (root.right != null && root.right.val != root.val) {
return false;
}
++ans;
return true;
};
dfs(root);
return ans;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countUnivalSubtrees(root *TreeNode) (ans int) {
var dfs func(*TreeNode) bool
dfs = func(root *TreeNode) bool {
if root == nil {
return true
}
l, r := dfs(root.Left), dfs(root.Right)
if !l || !r {
return false
}
if root.Left != nil && root.Left.Val != root.Val {
return false
}
if root.Right != nil && root.Right.Val != root.Val {
return false
}
ans++
return true
}
dfs(root)
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Validation | O(n^2) | O(h) | Conceptual starting point to understand subtree validation logic |
| Postorder DFS with State Propagation | O(n) | O(h) | Optimal solution for interviews and production tree traversal problems |
Frequently asked questions
Is Count Univalue Subtrees easy or hard?
Count Univalue Subtrees is considered a medium difficulty problem. The challenge comes from recognizing that postorder traversal is required and designing a recursive function that returns subtree validity while counting results efficiently.
Count Univalue Subtrees Python/Java solution
Python and Java solutions typically implement a recursive postorder DFS function that returns whether a subtree is univalue. A shared counter variable tracks how many valid subtrees are found while traversing the tree once in O(n) time.
How to solve Count Univalue Subtrees in O(n)?
Use a postorder DFS traversal. Process the left and right subtrees first, then determine whether the current node forms a univalue subtree by comparing its value with its children. Return a boolean indicating subtree validity and increment a counter whenever a valid univalue subtree is found.
What is the best approach for Count Univalue Subtrees?
The best approach uses postorder depth-first search. Each recursive call determines whether the current subtree is univalue by checking results from the left and right children. If both subtrees are univalue and their values match the current node, increment the counter. This solution runs in O(n) time and O(h) space.
Is Count Univalue Subtrees asked at Google/Amazon/Meta?
Tree DFS problems similar to Count Univalue Subtrees appear in interviews at companies like Amazon, Google, and Meta. Interviewers use these questions to evaluate recursive thinking, tree traversal skills, and the ability to propagate state during DFS.
What data structure is used in Count Univalue Subtrees?
The problem uses a binary tree as the primary data structure. The algorithm relies on depth-first search traversal, typically implemented with recursion and a counter variable to track valid univalue subtrees.
What is the time complexity of Count Univalue Subtrees?
The optimal solution runs in O(n) time because each node in the binary tree is visited exactly once during the DFS traversal. Space complexity is O(h), where h is the height of the tree due to the recursion stack.