algoadvance

Leetcode 2236. Root Equals Sum of Children

Problem Statement

Given a binary tree where the root node has an integer value val and two children with their own integer values left and right, determine if the value of the root node is equal to the sum of its children. The tree is guaranteed to have exactly three nodes: the root, its left child, and its right child.

Clarifying Questions

1. Input Constraints:
   • Are the integers in the nodes always non-negative?
   • Can the value of the nodes be zero?
   • Is the structure of the tree guaranteed to always be valid as described (exactly three nodes)?
2. Output Constraints:
   • Should the output be a boolean value indicating whether the root value equals the sum of the children’s values?

Given the typical problem constraints and based on LeetCode’s platform, these assumptions will be considered:

• The tree consists exactly of three nodes.
• Node values are valid integers.
• The function will return a boolean value.

Code

/**
 * 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 checkTree(TreeNode* root) {
        if (root == nullptr || root->left == nullptr || root->right == nullptr) {
            return false;
        }
        return (root->val == root->left->val + root->right->val);
    }
};

Strategy

1. Tree Structure Validation:
   • Ensure the root and its children are not null. However, given the problem constraints, this validation can be seen as redundant but is included for fault tolerance.
2. Summation Check:
   • Calculate the sum of the values stored in root->left->val and root->right->val.
   • Compare this calculated sum to root->val.
   • Return true if they are equal, otherwise false.

Time Complexity

The time complexity of this solution is (O(1)) because:

• The operation consists of a few constant-time checks and a simple arithmetic operation.
• There is no traversal or recursion over the tree, hence no dependency on input size (which is fixed to three nodes).

The space complexity is also (O(1)) because only a constant amount of extra space is used.

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?