Domain 1EasyCORE

Univalued Binary Tree

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

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 (true or false) 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:

  1. Define a helper function is_unival_tree(node, val) that checks if the subtree rooted at node is univalued and all nodes have the value val.
  2. If the current node is None, return true because an empty tree is trivially univalued.
  3. Check if the current node’s value matches the expected value val. If not, return false.
  4. Recursively check the left and right subtrees with the same expected value val.
  5. The main function isUnivalTree(root) initializes the recursive process by calling is_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 true because 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 return true by default, which aligns with the trivially univalued property.