Approach: Compare every node against the root value

def isUnivalTree(self, root):
    def dfs(node):
        if not node: return True
        if node.val != root.val: return False
        return dfs(node.left) and dfs(node.right)
    return dfs(root)

Complexity: O(n) time, O(h) space.

Full Solution — all languages

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):
        def dfs(node):
            if not node: return True
            if node.val != root.val: return False
            return dfs(node.left) and dfs(node.right)
        return dfs(root)

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        rootVal = root.val;
        return dfs(root);
    }
    int rootVal;
    private boolean dfs(TreeNode node) {
        if (node == null) return true;
        if (node.val != rootVal) return false;
        return dfs(node.left) && dfs(node.right);
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: bool isUnivalTree(TreeNode* root) {
        int rv = root->val;
        function<bool(TreeNode*)> dfs = [&](TreeNode* node) -> bool {
            if (!node) return true;
            if (node->val != rv) return false;
            return dfs(node->left) && dfs(node->right);
        };
        return dfs(root);
    }
};

/**
 * Tree node shape: { val, left, right }
 * @param {TreeNode} root
 * @return {boolean}
 */ var isUnivalTree = function(root) {
    const dfs = (node) => {
        if (!node) return true;
        if (node.val !== root.val) return false;
        return dfs(node.left) && dfs(node.right);
    };
    return dfs(root);
};

Univalued Binary Tree

Example 1

Example 2

Constraints