Jobs

Interviews

Discussions

Root Equals Sum of Children

#993 Most AskedEasy

Root Equals Sum of Children #993 Most Asked

Easy

Google

5 views

Topics:

Trees

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6]
Output: true
Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.
10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1]
Output: false
Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.
5 is not equal to 3 + 1, so we return false.

Constraints:

The tree consists only of the root, its left child, and its right child.
-100 <= Node.val <= 100

Try coding it in LeetCode

Root Equals Sum of Children

#993 Most AskedEasy

Root Equals Sum of Children #993 Most Asked

Easy

Google

5 views

Topics:

Trees

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6]
Output: true
Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.
10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1]
Output: false
Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.
5 is not equal to 3 + 1, so we return false.

Constraints:

The tree consists only of the root, its left child, and its right child.
-100 <= Node.val <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the node values be negative, zero, or only positive integers?
What are the constraints on the number of nodes in the binary tree?
If the root's value is null or if either child is null, what should I return?
Can the tree be unbalanced?
Should I handle cases where the root node has only one child (either left or right)?

Brute Force Solution

Approach

We need to check if the value of a tree's root node is equal to the sum of its left and right children's values. The most straightforward way is to simply get the value of each of the three nodes and perform the sum.

Here's how the algorithm would work step-by-step:

First, find the value of the main node, which we'll call the root.
Next, find the value of the node on the left, which we'll call the left child.
Then, find the value of the node on the right, which we'll call the right child.
After you have all three values, add the value of the left child to the value of the right child.
Finally, check if the sum of the two children's values is the same as the root's value. If they're equal, the answer is yes; otherwise, the answer is no.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def root_equals_sum_of_children(root: TreeNode) -> bool:
    root_value = root.val

    # Handle cases where there are missing children
    left_child_value = root.left.val if root.left else 0
    
    # Handle cases where there are missing children
    right_child_value = root.right.val if root.right else 0

    # Calculate the sum of the left and right children
    children_sum = left_child_value + right_child_value

    # Check if root value is equal to the children's sum
    return root_value == children_sum

Big(O) Analysis

Time Complexity

O(1) – The algorithm accesses the value of the root node, its left child, and its right child. These are all constant-time operations, regardless of the overall size of the tree. The sum and comparison are also constant-time operations. Therefore, the time complexity is O(1), constant time.

Space Complexity

O(1) – The algorithm only uses three variables to store the root value, the left child's value, and the right child's value. The space used by these variables is independent of the number of nodes in the tree (N). Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The problem asks us to check if the value of a tree's root node is equal to the sum of its left and right child nodes. We simply need to access these values and perform a single addition and comparison. This is a direct application of the problem's condition.

Here's how the algorithm would work step-by-step:

Get the value of the root node.
Get the value of the left child node.
Get the value of the right child node.
Add the left child's value and the right child's value together.
Check if the sum from the previous step is equal to the root's value.
Return 'true' if they are equal, otherwise return 'false'.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def root_equals_sum_of_children(root: TreeNode) -> bool:
    root_node_value = root.val
    left_child_value = root.left.val
    right_child_value = root.right.val

    # Summing child node values is required by problem
    sum_of_children = left_child_value + right_child_value

    # Root must equal sum of children, as defined
    if root_node_value == sum_of_children:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(1) – The algorithm performs a fixed number of operations regardless of the size of the tree. It accesses the root node's value and the values of its left and right children, performs one addition, and one comparison. Since the number of operations is constant and independent of any input size n, the time complexity is O(1).

Space Complexity

O(1) – The provided solution only uses a few variables to store the values of the root, left child, and right child, along with the sum. The number of these variables does not depend on the number of nodes in the tree. Therefore, the auxiliary space used remains constant regardless of the size of the input tree (N), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null root node	Return true if the root is null as it trivially satisfies the condition (or define the behavior as false in the problem definition).
Root node with null left and right children	Return true if both children are null, because their implicit sum is zero and the root's value can be zero.
Integer overflow when summing children's values	Use a larger data type (e.g., long) for the sum to prevent overflow if the values could be close to max int.
Large binary tree causing stack overflow with recursive approach	Implement an iterative solution (e.g., using a stack or queue) to avoid potential stack overflow issues.
One child is null and the root's value is non-zero	Treat a null child's value as 0 and continue the sum calculation.
Negative node values present in the binary tree	The algorithm should correctly handle negative values during the sum calculation.
Root value is zero, and children's sum is non-zero	The algorithm correctly returns false if the children's sum does not equal the root's zero value.
Perfectly balanced tree with large values	The algorithm should handle deeply nested trees without performance degradation, considering the time complexity O(1).

Null root node

How to Handle:

Return true if the root is null as it trivially satisfies the condition (or define the behavior as false in the problem definition).

Root node with null left and right children

How to Handle:

Return true if both children are null, because their implicit sum is zero and the root's value can be zero.

Integer overflow when summing children's values

How to Handle:

Use a larger data type (e.g., long) for the sum to prevent overflow if the values could be close to max int.

Large binary tree causing stack overflow with recursive approach

How to Handle:

Implement an iterative solution (e.g., using a stack or queue) to avoid potential stack overflow issues.

One child is null and the root's value is non-zero

How to Handle:

Treat a null child's value as 0 and continue the sum calculation.

Negative node values present in the binary tree

How to Handle:

The algorithm should correctly handle negative values during the sum calculation.

Root value is zero, and children's sum is non-zero

How to Handle:

The algorithm correctly returns false if the children's sum does not equal the root's zero value.

Perfectly balanced tree with large values

How to Handle:

The algorithm should handle deeply nested trees without performance degradation, considering the time complexity O(1).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the node values be negative, zero, or only positive integers?
What are the constraints on the number of nodes in the binary tree?
If the root's value is null or if either child is null, what should I return?
Can the tree be unbalanced?
Should I handle cases where the root node has only one child (either left or right)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, find the value of the main node, which we'll call the root.
Next, find the value of the node on the left, which we'll call the left child.
Then, find the value of the node on the right, which we'll call the right child.
After you have all three values, add the value of the left child to the value of the right child.
Finally, check if the sum of the two children's values is the same as the root's value. If they're equal, the answer is yes; otherwise, the answer is no.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def root_equals_sum_of_children(root: TreeNode) -> bool:
    root_value = root.val

    # Handle cases where there are missing children
    left_child_value = root.left.val if root.left else 0
    
    # Handle cases where there are missing children
    right_child_value = root.right.val if root.right else 0

    # Calculate the sum of the left and right children
    children_sum = left_child_value + right_child_value

    # Check if root value is equal to the children's sum
    return root_value == children_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Get the value of the root node.
Get the value of the left child node.
Get the value of the right child node.
Add the left child's value and the right child's value together.
Check if the sum from the previous step is equal to the root's value.
Return 'true' if they are equal, otherwise return 'false'.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def root_equals_sum_of_children(root: TreeNode) -> bool:
    root_node_value = root.val
    left_child_value = root.left.val
    right_child_value = root.right.val

    # Summing child node values is required by problem
    sum_of_children = left_child_value + right_child_value

    # Root must equal sum of children, as defined
    if root_node_value == sum_of_children:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return true if the root is null as it trivially satisfies the condition (or define the behavior as false in the problem definition).
Root node with null left and right children	Return true if both children are null, because their implicit sum is zero and the root's value can be zero.
Integer overflow when summing children's values	Use a larger data type (e.g., long) for the sum to prevent overflow if the values could be close to max int.
Large binary tree causing stack overflow with recursive approach	Implement an iterative solution (e.g., using a stack or queue) to avoid potential stack overflow issues.
One child is null and the root's value is non-zero	Treat a null child's value as 0 and continue the sum calculation.
Negative node values present in the binary tree	The algorithm should correctly handle negative values during the sum calculation.
Root value is zero, and children's sum is non-zero	The algorithm correctly returns false if the children's sum does not equal the root's zero value.
Perfectly balanced tree with large values	The algorithm should handle deeply nested trees without performance degradation, considering the time complexity O(1).

Null root node

How to Handle:

Return true if the root is null as it trivially satisfies the condition (or define the behavior as false in the problem definition).

Root node with null left and right children

How to Handle:

Return true if both children are null, because their implicit sum is zero and the root's value can be zero.

Integer overflow when summing children's values

How to Handle:

Use a larger data type (e.g., long) for the sum to prevent overflow if the values could be close to max int.

Large binary tree causing stack overflow with recursive approach

How to Handle:

Implement an iterative solution (e.g., using a stack or queue) to avoid potential stack overflow issues.

One child is null and the root's value is non-zero

How to Handle:

Treat a null child's value as 0 and continue the sum calculation.

Negative node values present in the binary tree

How to Handle:

The algorithm should correctly handle negative values during the sum calculation.

Root value is zero, and children's sum is non-zero

How to Handle:

The algorithm correctly returns false if the children's sum does not equal the root's zero value.

Perfectly balanced tree with large values

How to Handle:

The algorithm should handle deeply nested trees without performance degradation, considering the time complexity O(1).

0/1916 Google questions completed

0/1916 completed