Univalued Binary Tree solution and explanation
Google
9 more videos on this problem
Univalued Binary Tree || Leetcode 965Code with Newton · 6:17 · 1K views
LeetCode 965 | Univalued Binary Tree | Solution Explained (Java)Xavier Elon · 4:18 · 853 views
965. Univalued Binary Tree | LEETCODE EASYcode Explainer · 2:48 · 491 views
965. Univalued Binary Tree (Leetcode Easy)Programming Live with Larry · 3:30 · 482 views
Leetcode 965 | Univalued Binary Tree (Java Solution)The Tech Granth · 3:45 · 314 views
965. Univalued Binary Tree | Leetcode | Tree | EasyChhavi Bansal · 5:11 · 279 views
Univalued Binary Tree | Leetcode 965 | Amazon Google Facebook interview questionSuper Lazy Coder · 6:35 · 206 views
Univalued Binary Tree - LeetCode 965 ExplainedAlvin The Programmer · 12:47 · 164 views
965. Univalued Binary Tree LeetCode Tree Based ProblemCoding Gist · 5:15 · 133 views
LEETCODE - Univalued Binary Tree Complete - JAVASCRIPTIan Rosen · 7:47 · 122 views
The problem
A binary tree is uni-valued if every node in the tree has the same value.
Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.
Example 1:
Input: root = [1,1,1,1,1,null,1] Output: true
Example 2:
Input: root = [2,2,2,5,2] Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. 0 <= Node.val < 100
Approach overview
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.
Approach 1: Recursive Depth-First Search (DFS)
The recursive DFS approach involves starting from the root and checking if every node has the same value as the root node. This can be achieved by recursively checking the left and right subtrees of each node. If a node value differs from the root node's value, we return false immediately.
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool:
def isUnival(node, val):
if not node:
return True
if node.val != val:
return False
return isUnival(node.left, val) and isUnival(node.right, val)
return isUnival(root, root.val)class Solution {
public boolean isUnivalTree(TreeNode root) {
return isUnivalTree(root, root.val);
}
private boolean isUnivalTree(TreeNode node, int val) {
if (node == null) return true;
if (node.val != val) return false;
return isUnivalTree(node.left, val) && isUnivalTree(node.right, val);
}
}class Solution {
public:
bool isUnival(TreeNode* root, int value) {
if (root == nullptr) return true;
if (root->val != value) return false;
return isUnival(root->left, value) && isUnival(root->right, value);
}
bool isUnivalTree(TreeNode* root) {
return isUnival(root, root->val);
}
};var isUnivalTree = function(root) {
function dfs(node, val) {
if (node === null) return true;
if (node.val !== val) return false;
return dfs(node.left, val) && dfs(node.right, val);
}
return dfs(root, root.val);
};bool isUnival(TreeNode* root, int value) {
if (root == NULL) return true;
if (root->val != value) return false;
return isUnival(root->left, value) && isUnival(root->right, value);
}
bool isUnivalTree(TreeNode* root) {
return isUnival(root, root->val);
}public class Solution {
public bool IsUnivalTree(TreeNode root) {
return IsUnivalTree(root, root.val);
}
private bool IsUnivalTree(TreeNode node, int value) {
if (node == null) return true;
if (node.val != value) return false;
return IsUnivalTree(node.left, value) && IsUnivalTree(node.right, value);
}
}The isUnivalTree() method employs a nested function to recursively verify each node's value against the root's value, enabling a recursive DFS solution in Python.
Time Complexity: O(n), since every node is traversed once.
Space Complexity: O(h), with h as the tree's height due to the function calls on stack.
Approach 2: Iterative Breadth-First Search (BFS)
An iterative BFS approach uses a queue to level-order traverse the tree. We compare each node's value to the root's value. If any node differs, the function returns false.
from collections import deque
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool:
val = root.val
queue = deque([root])
while queue:
node = queue.popleft()
if node.val != val:
return False
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return Trueimport java.util.LinkedList;
import java.util.Queue;
class Solution {
public boolean isUnivalTree(TreeNode root) {
int val = root.val;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.val != val) return false;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
return true;
}
}#include <queue>
class Solution {
public:
bool isUnivalTree(TreeNode* root) {
int value = root->val;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node->val != value) return false;
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
return true;
}
};var isUnivalTree = function(root) {
let value = root.val;
let queue = [root];
while (queue.length > 0) {
let node = queue.shift();
if (node.val !== value) return false;
if (node.left !== null) queue.push(node.left);
if (node.right !== null) queue.push(node.right);
}
return true;
};#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
bool isUnivalTree(TreeNode* root) {
int value = root->val;
TreeNode* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
if (node->val != value) return false;
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
return true;
}using System.Collections.Generic;
public class Solution {
public bool IsUnivalTree(TreeNode root) {
int val = root.val;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
TreeNode node = queue.Dequeue();
if (node.val != val) return false;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return true;
}
}Using Python's collections.deque as a queue, this solution explores nodes in breadth-first order, matching node values with the root.
Time Complexity: O(n) since each node is examined once.
Space Complexity: O(n) due to the queue storing nodes of the tree level at once.
Approach 3: DFS
We denote the value of the root node as x, and then design a function dfs(root), which indicates whether the current node's value is equal to x and its left and right subtrees are also univalued binary trees.
In the function dfs(root), if the current node is null, return true; otherwise, if the current node's value is equal to x and its left and right subtrees are also univalued binary trees, return true; otherwise, return false.
In the main function, we call dfs(root) and return the result.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isUnivalTree(root: TreeNode | null): boolean {
const x = root!.val;
const dfs = (root: TreeNode | null): boolean => {
if (!root) {
return true;
}
return root.val === x && dfs(root.left) && dfs(root.right);
};
return dfs(root);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isUnivalTree(root *TreeNode) bool {
x := root.Val
var dfs func(*TreeNode) bool
dfs = func(root *TreeNode) bool {
if root == nil {
return true
}
return root.Val == x && dfs(root.Left) && dfs(root.Right)
}
return dfs(root)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn is_unival_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
let x = root.as_ref().unwrap().borrow().val;
fn dfs(node: Option<Rc<RefCell<TreeNode>>>, x: i32) -> bool {
if let Some(n) = node {
let n = n.borrow();
n.val == x && dfs(n.left.clone(), x) && dfs(n.right.clone(), x)
} else {
true
}
}
dfs(root, x)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), since every node is traversed once. |
| Iterative Breadth-First Search (BFS) | Time Complexity: O(n) since each node is examined once. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best default approach for binary trees. Clean recursive logic and minimal code. |
| Iterative Breadth-First Search (BFS) | O(n) | O(n) | Useful when recursion depth may be large or when practicing queue-based tree traversal. |
Frequently asked questions
Is Univalued Binary Tree easy or hard?
Univalued Binary Tree is classified as an Easy problem. It mainly tests understanding of binary tree traversal and simple value comparisons rather than complex algorithms.
Univalued Binary Tree Python/Java solution
In Python or Java, store the root value and traverse the tree using recursion (DFS) or a queue (BFS). Compare each node's value with the stored value and return false if any mismatch occurs. Both implementations run in O(n) time.
How to solve Univalued Binary Tree in O(n)?
Traverse the tree using DFS or BFS while comparing each node's value to the root value. If any node differs, return false immediately. Since each node is processed once and the comparison is constant time, the total complexity remains O(n).
What is the best approach for Univalued Binary Tree?
Recursive Depth-First Search (DFS) is the most common solution. Store the root value and recursively compare it with every node in the tree. Each node is visited once, giving O(n) time complexity with O(h) recursion stack space where h is the tree height.
Is Univalued Binary Tree asked at Google/Amazon/Meta?
Univalued Binary Tree is a common easy-level tree traversal problem used in technical interviews and practice platforms. Variations of tree validation problems frequently appear in interviews at companies like Amazon, Google, and Meta to test understanding of recursion and traversal techniques.
What data structure is used in Univalued Binary Tree?
The problem uses a binary tree data structure. The solution typically relies on traversal techniques such as Depth-First Search using recursion or Breadth-First Search using a queue to visit every node.
What is the time complexity of Univalued Binary Tree?
The time complexity is O(n) because every node in the binary tree must be checked at least once. Both DFS and BFS traversals visit each node exactly one time to verify that all values match the root value.