algoadvance

Leetcode 965. Univalued Binary Tree

Problem Statement:

Given a binary tree, determine if it is a univalued binary tree. A binary tree is univalued if every node in the tree has the same value.

Clarifying Questions:

1. What is the definition of the “value” of a node?
   • The value of a node is an integer associated with each node in the tree.
2. What should be the output if the tree is empty?
   • If the tree is empty, we consider it univalued, so the output should be true.
3. Can the node contain negative values?
   • Yes, nodes can contain negative values.
4. Is there a limit to the depth of the tree?
   • Generally, no strict limit in practical terms, but the solution should handle typical binary tree depths efficiently.

Strategy:

1. Recursive Approach:
   • Use a recursive approach to compare the value of each node with the value of the root node.
   • Define a helper function to perform this comparison for each node and its children.
2. Base Case:
   • If the current node is null, return true because an empty subtree is trivially univalued.
3. Recursive Case:
   • Compare the current node’s value with the root’s value.
   • Also, recursively check the left and right subtrees.

Code:

/**
* 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;
*     }
* }
*/

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

Time Complexity:

• Time Complexity: O(n) where n is the number of nodes in the tree. Each node is visited exactly once.
• Space Complexity: O(h) where h is the height of the tree. This is due to the recursion stack used in the depth-first traversal.

This solution efficiently checks every node’s value against the root’s value to determine if the binary tree is univalued.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?