Problem Description

You are given a binary tree with exactly 3 nodes: a root node, a left child node, and a right child node.

Your task is to check if the value of the root node equals the sum of the values of its two children.

Return true if root.val == left.val + right.val, otherwise return false.

For example:

• If the root has value 10, left child has value 4, and right child has value 6, then return true (since 4 + 6 = 10)
• If the root has value 5, left child has value 3, and right child has value 1, then return false (since 3 + 1 ≠ 5)

The solution directly accesses the root node's value and compares it with the sum of its left and right children's values in a single line: root.val == root.left.val + root.right.val.

Intuition

This problem is straightforward since we have a fixed structure - exactly 3 nodes in the tree. We don't need to traverse the tree or handle edge cases like missing nodes or deeper levels.

The key insight is that we can directly access all three nodes from the root:

• The root node itself gives us the target sum
• The left child and right child are immediately accessible via root.left and root.right

Since the problem guarantees exactly 3 nodes exist, we don't need to check for null values or validate the tree structure. We can simply:

1. Get the root's value
2. Get the sum of the left and right children's values
3. Compare if they are equal

This leads to the one-line solution: check if root.val == root.left.val + root.right.val. The simplicity comes from the problem's constraints - with exactly 3 nodes, we avoid all the complexity that typically comes with tree problems like recursion, traversal, or handling varying tree depths.

Learn more about Tree and Binary Tree patterns.

Solution Approach

The implementation is direct and uses no additional data structures or complex algorithms. Here's the step-by-step approach:

1. Access the root node's value: We get root.val which represents the value we need to verify against the sum.

2. Calculate the sum of children: We access root.left.val and root.right.val to get the values of both child nodes, then add them together.

3. Perform the comparison: We use the equality operator == to check if the root's value equals the sum of its children.

The complete implementation in one line:

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

This solution leverages:

• Direct property access: Since Python's TreeNode class stores values as properties, we can directly access .val on each node
• Boolean expression evaluation: The expression root.val == root.left.val + root.right.val evaluates to either True or False, which is exactly what we need to return

Time Complexity: O(1) - We perform a constant number of operations regardless of input Space Complexity: O(1) - We don't use any extra space beyond the input

The beauty of this solution lies in its simplicity - no loops, no recursion, no auxiliary variables. Just a straightforward mathematical check that takes advantage of the problem's constraint of having exactly 3 nodes.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example Tree:

      10
     /  \
    4    6

Step-by-step execution:

1. Access the root node's value

   • We access root.val which gives us 10
   • This is the target value we need to verify

2. Calculate the sum of children

   • Access left child: root.left.val gives us 4
   • Access right child: root.right.val gives us 6
   • Calculate the sum: 4 + 6 = 10

3. Perform the comparison

   • Check if root.val == root.left.val + root.right.val
   • Substitute values: 10 == 4 + 6
   • Evaluate: 10 == 10 → true

The function returns true since the root's value equals the sum of its children.

Counter-example:

       5
      / \
     3   1

• Root value: 5
• Sum of children: 3 + 1 = 4
• Comparison: 5 == 4 → false

The function returns false since 5 does not equal 4.

The entire check happens in a single expression without any intermediate steps, loops, or recursive calls - just direct property access and arithmetic comparison.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm performs a constant number of operations:

• Access root.val - O(1)
• Access root.left.val - O(1)
• Access root.right.val - O(1)
• Perform one addition operation - O(1)
• Perform one comparison operation - O(1)

Since all operations are constant time and there's no recursion or iteration, the overall time complexity is O(1).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• No additional data structures are created
• No recursive calls are made (so no recursion stack)
• Only performs a simple calculation and comparison using the existing tree nodes

Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Null Pointer/Attribute Errors

The most common pitfall is assuming that the left and right children always exist. If either root.left or root.right is None, the code will throw an AttributeError when trying to access .val on a None object.

Example scenario that causes error:

root = TreeNode(5)
root.left = TreeNode(3)
root.right = None  # Missing right child
# This will raise: AttributeError: 'NoneType' object has no attribute 'val'

Solution: Add null checks before accessing child values:

def checkTree(self, root: Optional[TreeNode]) -> bool:
    if not root or not root.left or not root.right:
        return False
    return root.val == root.left.val + root.right.val

2. Integer Overflow in Other Languages

While Python handles arbitrarily large integers, in languages like Java or C++, adding two large integers could cause overflow. For example, if left.val = Integer.MAX_VALUE and right.val = 1, the sum would overflow.

Solution for languages with fixed integer sizes:

# Python equivalent of overflow-safe comparison
def checkTree(self, root: Optional[TreeNode]) -> bool:
    # Rearrange to avoid overflow: root.val - left.val == right.val
    return root.val - root.left.val == root.right.val

3. Assuming Binary Tree Structure

Developers might mistakenly try to apply this solution to trees with more than 3 nodes or trees where nodes might have only one child, not realizing the problem specifically guarantees exactly 3 nodes.

Solution: Document the constraint clearly and validate if needed:

def checkTree(self, root: Optional[TreeNode]) -> bool:
    # This solution assumes exactly 3 nodes as per problem constraints
    # For general trees, you'd need recursive traversal
    assert root and root.left and root.right, "Tree must have exactly 3 nodes"
    assert not root.left.left and not root.left.right, "Left child must be a leaf"
    assert not root.right.left and not root.right.right, "Right child must be a leaf"
    return root.val == root.left.val + root.right.val