Code Implementation

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

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        return dfs(root, root->val);
    }
private:
    bool dfs(TreeNode* node, int value) {
        if (!node) return true;
        if (node->val != value) return false;
        return dfs(node->left, value) && dfs(node->right, value);
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
var isUnivalTree = function(root) {
    function dfs(node, value) {
        if (!node) return true;
        if (node.val !== value) return false;
        return dfs(node.left, value) && dfs(node.right, value);
    }
    return dfs(root, root.val);
};
      

Problem Description

You are given the root of a binary tree, represented by the variable root. Your task is to determine whether all nodes of the tree have the same value. If every node in the tree contains the same integer value, the tree is called univalued. Return true if the tree is univalued and false otherwise.

• There is only one valid answer for each input.
• You cannot reuse or skip nodes; you must check every node in the tree.
• The input is a binary tree, so each node has at most two children.

Thought Process

To solve this problem, the first idea is to check every node in the binary tree to see if its value matches the root's value. A brute-force approach would be to traverse the entire tree and compare each node's value to the root's value.

However, we can optimize this by returning false as soon as we find a node that does not match the root's value, which avoids unnecessary checks. We can use either depth-first search (DFS) or breadth-first search (BFS) for traversal. DFS is often simpler for recursive solutions in binary trees.

In summary, our goal is to efficiently traverse the tree and stop early if a mismatch is found, ensuring we don't waste time after the answer is already determined.

Solution Approach

• Step 1: Start at the root node and record its value as the reference value.
• Step 2: Use a recursive function (DFS) to traverse the tree. For each node:
  • If the node is null, return true (since there's nothing to check).
  • If the node's value is not equal to the reference value, return false immediately.
  • Recursively check both left and right children.
• Step 3: If all nodes match the reference value, return true. If any mismatch is found, the recursion will bubble up false to the top.

We use recursion because it's a natural fit for tree traversal, and it allows us to check each node efficiently. The early return on mismatch ensures the algorithm is as fast as possible.

Example Walkthrough

Consider the following binary tree:

         1
        / \
       1   1
      / \
     1   1
  

• Step 1: The root's value is 1.
• Step 2: Visit the left child (value 1) — matches root.
• Visit the left child's left child (value 1) — matches root.
• Visit the left child's right child (value 1) — matches root.
• Visit the right child (value 1) — matches root.
• All nodes match, so the output is true.

Now, if one node had value 2 instead of 1, the recursion would return false as soon as it encounters that node, and the final result would be false.

Time and Space Complexity

• Brute-force approach: Still requires visiting every node, so the time complexity is O(N), where N is the number of nodes in the tree.
• Optimized approach: By returning early on mismatch, we may check fewer nodes, but in the worst case (all nodes match), we still visit every node: O(N) time.
• Space complexity: The recursion stack will be at most the height of the tree. For a balanced tree, this is O(log N); for a skewed tree, it could be O(N).

Both approaches have the same asymptotic time and space complexity, but the optimized approach can terminate earlier in practice.

Summary

To determine if a binary tree is univalued, we traverse the tree and compare each node's value to the root's value. By using a recursive DFS and returning early on the first mismatch, we efficiently solve the problem. This approach is elegant because it leverages the natural structure of binary trees and recursion, and it ensures we only do as much work as necessary to find the answer.