algoadvance

Leetcode 965. Univalued Binary Tree

Problem Statement

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

Given the root of a binary tree, return true if the tree is univalued, or false otherwise.

Clarifying Questions

  1. Node Value Range: What is the range of values for the nodes in the tree?
    • Answer: The problem does not explicitly state a range, but we can assume the values will fit within the standard range for integers in C++.
  2. Tree Structure: Can the tree be empty?
    • Answer: Yes, an empty tree is considered trivially univalued, and we should return true.
  3. Node Class Definition: What is the structure of the node class?
    • Answer: 
      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) {}
};

Strategy

To determine if a binary tree is univalued, we can perform a Depth-First Search (DFS) traversal (either recursively or iteratively). We can start from the root and check if every node in the tree has the same value as the root.

Steps:

  1. Store the value of the root node.
  2. Traverse the tree using DFS.
  3. At each node, check if the node’s value matches the root value.
  4. If a mismatch is found, return false immediately.
  5. If the traversal completes without finding any mismatches, return true.

Code

#include <iostream>

// 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) {
        // Base case: if root is nullptr, the tree is trivially univalued
        if (root == nullptr) return true;
        
        // Store the root's value
        int rootValue = root->val;
        
        // Helper function to perform DFS
        return dfs(root, rootValue);
    }
    
private:
    bool dfs(TreeNode* node, int val) {
        if (node == nullptr) return true;
        if (node->val != val) return false;
        return dfs(node->left, val) && dfs(node->right, val);
    }
};

int main() {
    // Example usage:
    // Constructing a univalued binary tree where all nodes have the value 1.
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(1);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(1);
    
    Solution sol;
    bool result = sol.isUnivalTree(root);
    std::cout << (result ? "True" : "False") << std::endl; // Output should be True
    
    return 0;
}

Time Complexity

The solution involves traversing every node in the binary tree once.

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