Univalued Binary Tree - Practice Coding Problems

Univalued Binary Tree - 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.

Input & Output

Example 1 — All Same Values

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

› Output: true

💡 Note: All nodes have value 1, so the tree is uni-valued

Example 2 — Different Values

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

› Output: false

💡 Note: One node has value 5 while others have value 2, so not uni-valued

Example 3 — Single Node

$ Input: root = [1]

› Output: true

💡 Note: A single node tree is always uni-valued

Constraints

The number of nodes in the tree is in the range [0, 100].
0 ≤ Node.val ≤ 99

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values to check

Compare Values

Check if all nodes have same value as root

Return Result

True if all same, false if any differ

Key Takeaway

🎯 Key Insight: Compare all nodes against root value - stop early on first mismatch

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that all nodes must have the same value as the root. Best approach is DFS with early termination - compare each node with the root's value during traversal. Time: O(n), Space: O(h)

Common Approaches

Approach	Time	Space	Notes
✓ BFS - Level Order Traversal	O(n)	O(w)	Use queue-based BFS to check each level, comparing with root value
DFS - One Pass Comparison	O(n)	O(h)	Compare each node with root value during single DFS traversal
Brute Force - Compare All Nodes	O(n)	O(n)	Collect all node values and check if they're all equal

BFS - Level Order Traversal — Algorithm Steps

Step 1: Initialize queue with root and store target value
Step 2: Process each level, comparing nodes with target
Step 3: Return false immediately if any node differs

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start with root in queue, store target value

Process Levels

Check each node against target, add children to queue

Early Return

Return false on first mismatch

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

bool solution(struct TreeNode* root) {
    if (!root) return true;
    
    int targetVal = root->val;
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        
        if (node->val != targetVal) return false;
        
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
    
    return true;
}

int main() {
    printf("true\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once, may terminate early on mismatch

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum tree width

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS - Level Order Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler