Univalued Binary Tree - Leetcode Solution

Problem Statement: A binary tree is univalued if every node in the tree has the same value.

Return true if and only if the given tree is univalued.

Example 1: Input: [1,1,1,1,1,null,1] Output: true

Example 2: Input: [2,2,2,5,2] Output: false

Solution: To solve this problem, we need to traverse through every node in the given binary tree and check if all the values in the tree are the same. To do this, we can use a recursive approach where we check if the value of the root node is equal to the value of its left and right children. If it is true, then we recursively call the function on the left and right children until we reach the leaf nodes.

Algorithm:

1. Create a function isUnivalTree() that takes the root node of the binary tree as its input parameter.
2. Check if the root node is null, return true since an empty tree is considered univalued by default.
3. Call the function recursively on its left and right children.
4. Check if the value of the root node is equal to the value of its left and right children.
5. Return true if the values are equal, false otherwise.

Code:

bool isUnivalTree(TreeNode* root) { if (root == NULL) { return true; } if (root->left != NULL && root->val != root->left->val) { return false; } if (root->right != NULL && root->val != root->right->val) { return false; } return isUnivalTree(root->left) && isUnivalTree(root->right); }

Time complexity: O(n), where n is the number of nodes in the given binary tree. Space complexity: O(h), where h is the height of the binary tree.

1