#965

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Univalued Binary Tree

Determine if a binary tree is uni-valued using traversal and state tracking techniques.

tree depth first search breadth first search binary tree

Problem Statement

A binary tree is considered uni-valued if every node in the tree has the same value. Given the root of a binary tree, determine if the tree is uni-valued or not.

The tree traversal can be performed using either depth-first or breadth-first search techniques. While traversing, compare each node’s value with the root’s value to check for consistency.

Examples

Example 1

Input: root = [1,1,1,1,1,null,1]

Output: true

Example details omitted.

Example 2

Input: root = [2,2,2,5,2]

Output: false

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 100].
0 <= Node.val < 100

Solution Approach

Tree Traversal with DFS

Use Depth-First Search (DFS) to recursively traverse the tree. For each node, check if its value matches the root node’s value. If any node differs, return false. If traversal completes without discrepancies, return true.

Tree Traversal with BFS

Perform a Breadth-First Search (BFS) starting from the root. Use a queue to explore each node level by level. As with DFS, compare each node’s value with the root’s value. If any mismatch occurs, return false.

State Tracking During Traversal

Track the state of the node values as you traverse the tree. Compare each node to the root's value during traversal and track mismatches. A single discrepancy signals a false return.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(H)

Both DFS and BFS approaches have a time complexity of O(N), where N is the number of nodes in the tree. The space complexity is O(H), where H is the height of the tree, due to the recursive stack (for DFS) or the queue (for BFS).

What Interviewers Usually Probe

Can the candidate handle tree traversal techniques and manage state tracking effectively?
Does the candidate understand the importance of comparing node values in binary trees?
Can the candidate clearly explain the time and space complexity of the solution?

Common Pitfalls or Variants

Common pitfalls

Failing to correctly handle trees with multiple different node values.
Confusing DFS and BFS traversal, leading to inefficient or incorrect solutions.
Not addressing the space complexity of the recursive stack or queue.

Follow-up variants

Check for uni-valued binary trees with more complex structures, such as unbalanced trees.
Use a different tree traversal technique like iterative DFS to avoid stack overflow.
Optimize the space complexity by reducing the space required for traversal.

FAQ

What is the Univalued Binary Tree problem?

The Univalued Binary Tree problem asks you to determine if every node in a binary tree has the same value, using tree traversal techniques.

How can I solve the Univalued Binary Tree problem?

You can solve the problem by using either Depth-First Search (DFS) or Breadth-First Search (BFS) while checking if each node’s value matches the root’s value.

What is the time complexity of the Univalued Binary Tree solution?

The time complexity is O(N), where N is the number of nodes in the tree, as each node needs to be checked.

What is the space complexity of solving this problem?

The space complexity is O(H), where H is the height of the tree, due to the recursion stack (DFS) or the queue (BFS).

What common mistakes should I avoid in solving the Univalued Binary Tree problem?

Avoid failing to compare node values correctly, confusing traversal techniques, and not considering the space complexity of the traversal method.

terminal

Solution

Solution 1: DFS

We denote the value of the root node as $x$, and then design a function $\text{dfs}(\text{root})$, which indicates whether the current node's value is equal to $x$ and its left and right subtrees are also univalued binary trees.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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 isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        def dfs(root: Optional[TreeNode]) -> bool:
            if root is None:
                return True
            return root.val == x and dfs(root.left) and dfs(root.right)

        x = root.val
        return dfs(root)

Continue Practicing

#987 vertical order traversal of a binary tree #993 cousins in binary tree #865 smallest subtree with all the deepest nodes