Sponsored
Sponsored
The recursive DFS approach involves starting from the root and checking if every node has the same value as the root node. This can be achieved by recursively checking the left and right subtrees of each node. If a node value differs from the root node's value, we return false immediately.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
1class Solution {
2public:
3 bool isUnival(TreeNode* root, int value) {
4 if (root == nullptr) return true;
5 if (root->val != value) return false;
6 return isUnival(root->left, value) && isUnival(root->right, value);
7 }
8 bool isUnivalTree(TreeNode* root) {
9 return isUnival(root, root->val);
10 }
11};This C++ solution uses a helper function isUnival() to recursively check whether each subtree of a node contains only values equal to the tree's root value.
An iterative BFS approach uses a queue to level-order traverse the tree. We compare each node's value to the root's value. If any node differs, the function returns false.
Time Complexity: O(n), as each node is checked once.
Space Complexity: O(n), due to the queue storing at most one level of the tree.
1using System.Collections.Generic;
public class Solution {
public bool IsUnivalTree(TreeNode root) {
int val = root.val;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
TreeNode node = queue.Dequeue();
if (node.val != val) return false;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return true;
}
}This solution uses C#'s Queue from the System.Collections.Generic namespace for BFS, maintaining the current level nodes for checks against the root's value.