How do you solve Univalued Binary Tree on LeetCode?

Univalued Binary Tree (LeetCode #965) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: A binary tree is uni-valued if all nodes have the same value as the root.

What is the brute force solution for Univalued Binary Tree?

The brute force approach for Univalued Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The simplest way to check if a binary tree is uni-valued is to compare every node's value to the value of the root node. If any node has a different value, we return false. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Univalued Binary Tree?

Univalued Binary Tree uses the following concepts: Tree, Depth-First Search, Breadth-First Search, Binary Tree. The recommended patterns to study are: Depth-First Search, Breadth-First Search.

What are the interview tips for Univalued Binary Tree?

Clarify the definition of a uni-valued tree. Discuss your thought process and approach before coding. Consider edge cases, such as single-node trees.

What are common mistakes when solving Univalued Binary Tree?

Not handling null nodes properly. Assuming the tree is always non-empty.

#965

Univalued Binary Tree

Easy

TreeDepth-First SearchBreadth-First SearchBinary TreeDepth-First SearchBreadth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

We can traverse the tree once and check if all nodes have the same value as the root. This is efficient and avoids unnecessary repeated checks.

⚙️

Algorithm

4 steps

1Step 1: Get the value of the root node.
2Step 2: Use a Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the tree.
3Step 3: For each node, check if its value matches the root's value. If any node does not match, return false immediately.
4Step 4: If the traversal completes without mismatches, return true.

solution.py18 lines

1# Full working Python code
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
8def isUnivalTree(root):
9    if not root:
10        return True
11    value = root.val
12    def dfs(node):
13        if not node:
14            return True
15        if node.val != value:
16            return False
17        return dfs(node.left) and dfs(node.right)
18    return dfs(root)

ℹ

Complexity note: The time complexity is linear because we visit each node exactly once. The space complexity is also O(n) in the worst case due to the recursion stack.

1A binary tree is uni-valued if all nodes have the same value as the root.
2Using DFS or BFS ensures we check each node efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.