{x}
blog image

Univalued Binary Tree

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 1:

Input: root = [1,1,1,1,1,null,1]
Output: true

Example 2:

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

965. Univalued Binary Tree

Problem Description

Determine if a given binary tree is univalued, meaning all nodes have the same value.

Solution Approach: Depth-First Search (DFS)

The most efficient approach is to use Depth-First Search (DFS). We recursively traverse the tree, checking if each node's value matches the root's value.

Algorithm:

  1. Base Case: If the current node is null (empty), return true (empty subtrees are univalued).
  2. Value Check: Check if the current node's value is equal to the root node's value (x). If not, return false immediately.
  3. Recursive Calls: Recursively call the DFS function on the left and right subtrees. The entire subtree is univalued only if both recursive calls return true.

Time and Space Complexity:

  • Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be equal to N. In the best case (a balanced tree), H is log₂(N).

Code Implementation in Multiple Languages

Python

# 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: Optional[TreeNode]) -> bool:
        x = root.val  # Store the root's value for comparison
 
        def dfs(node):
            if not node:
                return True
            if node.val != x:
                return False
            return dfs(node.left) and dfs(node.right)
 
        return dfs(root)

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isUnivalTree(TreeNode root) {
        int x = root.val;
 
        return dfs(root, x);
    }
 
    private boolean dfs(TreeNode node, int x) {
        if (node == null) return true;
        if (node.val != x) return false;
        return dfs(node.left, x) && dfs(node.right, x);
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        int x = root->val;
        return dfs(root, x);
    }
 
    bool dfs(TreeNode* node, int x) {
        if (!node) return true;
        if (node->val != x) return false;
        return dfs(node->left, x) && dfs(node->right, x);
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isUnivalTree(root *TreeNode) bool {
    x := root.Val
    return dfs(root, x)
}
 
func dfs(node *TreeNode, x int) bool {
    if node == nil {
        return true
    }
    if node.Val != x {
        return false
    }
    return dfs(node.Left, x) && dfs(node.Right, x)
}

Javascript

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root) {
    const x = root.val;
    
    function dfs(node) {
        if (!node) return true;
        if (node.val !== x) return false;
        return dfs(node.left) && dfs(node.right);
    }
    
    return dfs(root);
};

These code examples all implement the same DFS algorithm, demonstrating its concise and efficient nature for solving this problem. Remember to adapt the TreeNode definition according to your specific environment and language.