965. Univalued Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 0
Acceptance rate: 67.9%
Problem Breakdown
The problem asks us to determine if a binary tree is univalued, meaning all nodes in the tree have the same value. The input is a binary tree, and the output should be a boolean indicating whether the tree is univalued or not.
Inputs:
- A binary tree with nodes having integer values ranging from 0 to 99.
- The number of nodes in the tree ranges from 1 to 100.
Outputs:
- A boolean value (
trueorfalse) indicating whether the tree is univalued.
Implicit Constraints and Edge Cases:
- An empty tree (though the problem specifies at least one node, this is worth considering).
- Trees with a single node.
- Trees where all nodes have the same value.
- Trees where not all nodes have the same value.
Intuition
A brute-force approach would involve traversing the entire tree and checking if each node’s value matches the root node’s value. This approach has a time complexity of O(n) because we visit every node, but it is straightforward and sufficient for this problem given the constraints (1 to 100 nodes).
The key insight is that we can use a recursive traversal to check the univalued property efficiently. By passing down the expected value from the parent node to its children, we can determine if the tree is univalued in a single pass.
Approach
We will use a depth-first search (DFS) approach with recursion. The algorithm works as follows:
- Define a helper function
is_unival_tree(node, val)that checks if the subtree rooted atnodeis univalued and all nodes have the valueval. - If the current node is
None, returntruebecause an empty tree is trivially univalued. - Check if the current node’s value matches the expected value
val. If not, returnfalse. - Recursively check the left and right subtrees with the same expected value
val. - The main function
isUnivalTree(root)initializes the recursive process by callingis_unival_tree(root, root.val).
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
- Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case (a skewed tree), this could be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isUnivalTree(root: TreeNode) -> bool:
def is_unival_tree(node, val):
if not node:
return True
if node.val != val:
return False
return (is_unival_tree(node.left, val) and
is_unival_tree(node.right, val))
return is_unival_tree(root, root.val)
Edge Cases Handled
- Single Node Tree: The function correctly returns
truebecause a single node tree is trivially univalued. - All Nodes with Same Value: The function correctly returns
true. - Nodes with Different Values: The function correctly returns
false. - Empty Tree (though not possible per problem constraints): If the root is
None, the function would returntrueby default, which aligns with the trivially univalued property.