Univalued Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree. The task is to determine whether every node in the tree contains the same value. If all nodes share the identical value, the tree is considered univalued. Return true if the tree satisfies this property, otherwise return false.

Since the constraint involves checking every node's value against a single reference value, the core idea is simple: traverse the tree and verify that no node deviates from the root value. Tree traversal techniques such as Depth-First Search and Breadth-First Search work well because they visit every node exactly once.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

Recursive DFS walks through the tree while comparing each node's value with the root's value. Start by storing root.val. Recursively check the left and right children. If a node is null, treat it as valid and return true. If a node’s value differs from the reference value, immediately return false. Otherwise, recursively validate both subtrees. The recursion stack uses O(h) space where h is the height of the tree, which becomes O(n) in the worst case of a skewed tree and O(log n) for balanced trees.

This approach is concise and maps naturally to the recursive structure of a binary tree. Each node is processed once, so the total runtime remains linear.

Approach 2: Iterative Breadth-First Search (BFS) (Time: O(n), Space: O(n))

Iterative BFS uses a queue to traverse the tree level by level. Push the root node into the queue and store its value as the reference. While the queue is not empty, remove the front node and compare its value to the reference. If the values differ, return false. Otherwise, push the node’s left and right children into the queue if they exist.

This method ensures every node is visited exactly once. The queue may temporarily store up to an entire level of the tree, which results in O(n) space in the worst case. BFS is useful if you prefer iterative logic or want explicit control over traversal without recursion.

Recommended for interviews: Recursive DFS is typically the expected solution because it is short, readable, and directly follows the recursive nature of trees. Implementing DFS shows strong understanding of tree traversal and recursion. BFS is equally correct and demonstrates familiarity with queue-based traversal, which interviewers also value when discussing alternatives.