Skip to content

Latest commit

 

History

History
79 lines (51 loc) · 2.69 KB

079.md

File metadata and controls

79 lines (51 loc) · 2.69 KB

2236. Root Equals Sum of Children

Difficulty: 🟢 Easy

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.

Examples:

Example 1:

079_01.png

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:

079_02.png

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

Solutions

O(1) solution

Python3

# 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 checkTree(self, root: Optional[TreeNode]) -> bool:
        return root.val == root.left.val + root.right.val

The given solution provides a recursive approach to check if the value of the root node is equal to the sum of the values of its two children.

Here is a step-by-step overview of the solution:

  1. Check if the root node is None. If it is, return False as there is no node to check.
  2. Check if the value of the root node is equal to the sum of the values of its left and right children.
  3. Recursively call the checkTree function for the left child of the root.
  4. Recursively call the checkTree function for the right child of the root.
  5. Return the result of the logical AND operation between step 2 and the results from steps 3 and 4.

Complexity Analysis

The time complexity for this solution is O(1) because we are only dealing with a fixed number of nodes (3 nodes) in the binary tree.

The space complexity is O(1) because we are not using any additional space that grows with the input.

Summary

The given solution provides a simple approach to check if the value of the root node in a binary tree is equal to the sum of the values of its two children. It recursively traverses the tree and performs the required checks. The solution has a time complexity of O(1) and a space complexity of O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.