{x}
blog image

Root Equals Sum of Children

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

Solution Explanation

This problem involves checking a simple binary tree with only three nodes: the root, its left child, and its right child. The task is to determine if the root's value is equal to the sum of its children's values.

The solution is straightforward:

  1. Access Node Values: We access the values of the root node (root.val), its left child (root.left.val), and its right child (root.right.val).

  2. Sum and Compare: We sum the values of the left and right children and compare the sum to the root's value.

  3. Return Result: If the root's value is equal to the sum of its children's values, we return true; otherwise, we return false.

Time and Space Complexity Analysis

Time Complexity: O(1). The algorithm performs a constant number of operations regardless of the input size (since the tree always has exactly three nodes).

Space Complexity: O(1). The algorithm uses a constant amount of extra space to store the variables holding the node values. It doesn't use any data structures whose size depends on the input.

Code in Different Languages

The provided code snippets demonstrate the solution in various programming languages. They all follow the same basic logic:

  • Python: The code is concise and directly reflects the problem's logic.

  • Java: The Java solution uses a similar approach. Note the definition of the TreeNode class.

  • C++: The C++ solution mirrors the Python and Java versions. The TreeNode structure is defined appropriately.

  • Go: The Go solution is exceptionally brief, leveraging Go's syntax effectively.

  • TypeScript: The TypeScript code clearly shows the type definitions and the core logic.

  • Rust: The Rust solution uses Rc (reference counting) and RefCell (mutable borrowing) to handle the tree node references efficiently, a common pattern in Rust for working with trees to prevent ownership issues.

  • C: The C code offers a compact implementation, consistent with C's style.

All solutions are highly efficient due to the problem's constraints. The constant-time complexity makes them suitable even for very large (though still three-node) trees.