LeetCode 2236 - Root Equals Sum of Children

This problem gives us a binary tree that always contains exactly three nodes. There is one root node, one left child, and one right child. We must determine whether the value stored in the root node is equal to the sum of the values stored in its two children.

leetcodeeasytreebinary-tree

LeetCode Problem 2236

Difficulty: 🟢 Easy
Topics: Tree, Binary Tree

Solution

Problem Understanding

This problem gives us a binary tree that always contains exactly three nodes. There is one root node, one left child, and one right child. We must determine whether the value stored in the root node is equal to the sum of the values stored in its two children.

In other words, if:

  • root.val is the value of the root node
  • root.left.val is the value of the left child
  • root.right.val is the value of the right child

then we must return:

true  if root.val == root.left.val + root.right.val
false otherwise

The input is represented as a binary tree, but because the problem guarantees there are exactly three nodes, we never need to worry about larger tree traversals, recursion depth, or missing intermediate nodes.

The constraints are very small:

  • The tree always has exactly three nodes
  • Node values are between -100 and 100

These constraints tell us several important things:

  • We do not need to optimize heavily for performance
  • Integer overflow is impossible in both Python and Go
  • The left and right child nodes are guaranteed to exist
  • We do not need null checks for missing children under normal problem conditions

An important observation is that the problem structure itself prevents many common tree edge cases. For example:

  • The tree cannot be empty
  • The root cannot be missing children
  • There are no deeper levels to process

However, a naive implementation could still make mistakes such as:

  • Comparing the wrong values
  • Forgetting to access child node values
  • Using multiplication or subtraction instead of addition
  • Accidentally traversing the tree unnecessarily

Because the input size is fixed and tiny, the cleanest solution is also the best solution.

Approaches

Brute Force Approach

A brute-force style solution would treat the input as a general binary tree problem. We could traverse the tree recursively, collect all node values into a list, then check whether the first value equals the sum of the remaining two values.

This works because the tree always contains exactly three nodes. After traversal:

  • The first collected value would be the root
  • The next two values would be the children
  • We could compare the values directly

Although this approach produces the correct answer, it performs unnecessary work. We do not need recursion, additional storage, or traversal logic because the problem already guarantees the exact tree structure.

Optimal Approach

The key observation is that the tree structure is fixed and extremely small. Since the root always has exactly two children, we can directly access their values and compare them immediately.

Instead of traversing the tree, we simply compute:

root.left.val + root.right.val

and compare the result with:

root.val

This is the simplest and most efficient possible solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Traverses the tree and stores values unnecessarily
Optimal O(1) O(1) Directly compares root value with child sum

Since n = 3, both approaches are effectively constant time in practice, but the direct comparison approach is cleaner and more appropriate.

Algorithm Walkthrough

  1. Access the value stored in the root node using root.val.

This is the value we must verify against the sum of the children. 2. Access the left child value using root.left.val.

The problem guarantees that the left child exists. 3. Access the right child value using root.right.val.

The problem also guarantees that the right child exists. 4. Add the two child values together.

This produces the expected sum that should match the root value. 5. Compare the child sum with the root value.

If they are equal, return True. Otherwise, return False.

Why it works

The problem definition directly states that the answer should be true exactly when:

root.val == root.left.val + root.right.val

The algorithm computes this condition directly and returns the result of the comparison. Since every required value is accessed exactly once and no other logic is involved, the algorithm is both correct and minimal.

Python Solution

# 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

from typing import Optional

class Solution:
    def checkTree(self, root: Optional[TreeNode]) -> bool:
        return root.val == root.left.val + root.right.val

The implementation directly follows the optimal algorithm.

The method accesses the root value through root.val. It then accesses the left and right child values using root.left.val and root.right.val.

The two child values are added together, and the result is compared with the root value. The comparison itself produces a Boolean value, which is returned immediately.

Because the problem guarantees that the tree always contains exactly three nodes, we do not need additional safety checks for missing children.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func checkTree(root *TreeNode) bool {
    return root.Val == root.Left.Val+root.Right.Val
}

The Go implementation is nearly identical to the Python version.

The main difference is Go's struct field naming convention. The node values are accessed using Val, Left, and Right instead of Python's lowercase attribute names.

The problem guarantees that both child pointers are non-nil, so no additional nil checks are required.

Worked Examples

Example 1

Input:

root = [10,4,6]

Tree structure:

      10
     /  \
    4    6

Step-by-step execution:

Step Expression Value
Read root value root.val 10
Read left child root.left.val 4
Read right child root.right.val 6
Compute child sum 4 + 6 10
Compare 10 == 10 True

Final result:

true

Example 2

Input:

root = [5,3,1]

Tree structure:

      5
     / \
    3   1

Step-by-step execution:

Step Expression Value
Read root value root.val 5
Read left child root.left.val 3
Read right child root.right.val 1
Compute child sum 3 + 1 4
Compare 5 == 4 False

Final result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only a few direct value accesses and one comparison are performed
Space O(1) No additional memory proportional to input size is used

The algorithm performs a constant number of operations regardless of input values. Since the tree always contains exactly three nodes, execution time and memory usage remain constant.

Test Cases

# Definition for testing
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):
        return root.val == root.left.val + root.right.val

solution = Solution()

# Example 1
root = TreeNode(10, TreeNode(4), TreeNode(6))
assert solution.checkTree(root) is True  # root equals child sum

# Example 2
root = TreeNode(5, TreeNode(3), TreeNode(1))
assert solution.checkTree(root) is False  # root does not equal child sum

# Zero values
root = TreeNode(0, TreeNode(0), TreeNode(0))
assert solution.checkTree(root) is True  # all zeros

# Negative values
root = TreeNode(-5, TreeNode(-2), TreeNode(-3))
assert solution.checkTree(root) is True  # negative numbers sum correctly

# Mixed positive and negative values
root = TreeNode(1, TreeNode(3), TreeNode(-2))
assert solution.checkTree(root) is True  # mixed sign values

# Boundary values
root = TreeNode(100, TreeNode(50), TreeNode(50))
assert solution.checkTree(root) is True  # upper boundary values

# Boundary failure case
root = TreeNode(-100, TreeNode(-50), TreeNode(-49))
assert solution.checkTree(root) is False  # near lower boundary but incorrect sum
Test Why
[10,4,6] Validates the basic successful case
[5,3,1] Validates the basic failure case
[0,0,0] Ensures zero handling works correctly
[-5,-2,-3] Verifies negative number addition
[1,3,-2] Tests mixed positive and negative values
[100,50,50] Tests upper constraint boundaries
[-100,-50,-49] Tests incorrect sum near lower boundary

Edge Cases

One important edge case involves negative values. Some implementations accidentally assume all values are positive, but the constraints explicitly allow negative integers. For example, a root value of -5 with children -2 and -3 should return True. The implementation handles this correctly because integer addition works normally for negative values.

Another important edge case is when all values are zero. A careless implementation might accidentally treat zero as a falsy or invalid value in conditional logic. Since this solution performs only direct arithmetic comparison, the case [0,0,0] is handled naturally and correctly.

A third edge case involves boundary values near -100 and 100. Some languages can experience integer overflow in large arithmetic operations, but the constraints here are extremely small. Both Python and Go safely handle these additions without any overflow concerns.

Finally, the problem guarantees that the root always has both left and right children. A generic binary tree implementation might include unnecessary null checks, but this solution relies on the problem constraints and accesses the children directly. This keeps the code concise and efficient while remaining fully correct for valid inputs.