LeetCode: 965. Univalued Binary Tree

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

Input:  [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

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool isUnivalTree(TreeNode* root) {
	return isUnivalTree(root, root->val);
}

bool isUnivalTree(TreeNode* root, int prev) {
    if (root == nullptr) return true;

    return  prev == root->val && 
    		isUnivalTree(root->left, prev) && 
    		isUnivalTree(root->right, prev);
}

Let's break down the code step by step:

1. The code defines a function bool isUnivalTree(TreeNode* root) which takes a pointer to the root node of a binary tree as input and returns a boolean value (true or false) indicating whether the tree is a univalued tree or not.
2. Now, let's look at the isUnivalTree function with two parameters: This function takes two parameters: root, which is a pointer to a current node in the tree, and prev, which is the value of the parent node (or the value that is considered "uniform" for the current tree).

• The first line of the function checks whether the root node is a nullptr, which means it's an empty node. If it is, it returns true, as an empty tree is considered univalued.
• The return statement is a bit more complex. It combines three conditions using the logical AND (&&) operator:

1. prev == root->val: This checks if the current node's value is the same as the value of its parent. This is important because for a tree to be univalued, all nodes should have the same value.
2. isUnivalTree(root->left, prev): This recursively checks if the left subtree is univalued with the same value prev.
3. isUnivalTree(root->right, prev): This recursively checks if the right subtree is univalued with the same value prev.If all three conditions are true, then the function returns true, indicating that the tree rooted at the current node is a univalued tree. Otherwise, it returns false.