Root Equals Sum of Children - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given the root of a binary tree. The task is simple: return true if the root node's value equals the sum of its left and right child values. Otherwise return false. The tree is guaranteed to have exactly three nodes: a root and two children.
Approach 1: Simple Direct Access and Comparison (O(1) time, O(1) space)
The most straightforward solution directly accesses the values of the root and its two children. Since the tree structure is fixed (root with left and right children), you don't need traversal. Read root.val, root.left.val, and root.right.val, compute the sum of the children, and compare it with the root value. This works because the problem guarantees the children exist, eliminating the need for null checks. The algorithm performs a constant number of operations and uses no additional memory, giving O(1) time complexity and O(1) space complexity. This is the cleanest and most common interview answer for simple tree validation problems.
Approach 2: Defensive Programming (O(1) time, O(1) space)
A slightly more robust version adds safety checks before accessing node values. Even though the problem guarantees two children, production-grade code often validates inputs. First check that root, root.left, and root.right are not null. Then compute root.left.val + root.right.val and compare it with root.val. The algorithm still runs in O(1) time because only three nodes are inspected, and it uses O(1) space since no additional data structures are required. This pattern is useful when working with real-world binary tree APIs where structure guarantees might not exist.
Recommended for interviews: The direct comparison approach is what interviewers typically expect. It shows you understand the problem constraints and avoid unnecessary traversal. Mentioning the defensive version demonstrates awareness of edge cases and production coding practices. For such constrained tree problems, recognizing that traversal is unnecessary is the key insight.
Approach 1: Simple Direct Access and Comparison
This approach leverages the simplicity of the tree structure, which consists of exactly three nodes. We directly access the left and right children of the root node and compare their sum to the root node's value. This approach works efficiently given the constraint of only 3 nodes.
In C, we define a structure for a tree node. The function checkTree checks if the value of the root node is equal to the sum of the values of its left and right children by directly accessing these fields.
Complexity
Time Complexity: O(1) - We perform a constant number of operations.
Space Complexity: O(1) - We do not use any additional space.
Approach 2: Defensive Programming
This approach is similar to the first but includes basic defensive programming by handling potential null pointers. Though the tree constraints guarantee non-null children, it showcases safe coding practices.
This solution adds checks to ensure the root, left, and right nodes exist to avoid segmentation faults. It then compares the root value against the combined children's values.
Complexity
Time Complexity: O(1) - Constant operations included.
Space Complexity: O(1) - No additional memory is utilized.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Simple Direct Access and Comparison | Time Complexity: O(1) - We perform a constant number of operations. |
| Defensive Programming | Time Complexity: O(1) - Constant operations included. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Direct Access and Comparison | O(1) | O(1) | Best for interviews when the tree structure is guaranteed to have root and two children. |
| Defensive Programming | O(1) | O(1) | When writing production-safe code where null checks are required. |
Video Solution
Root Equals Sum of Children | LeetCode 2236 | Cpp • CodeClips with Abhishek Ranjan • 1,347 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Root Equals Sum of Children easy or hard?
Root Equals Sum of Children Python/Java solution
How to solve Root Equals Sum of Children in O(n)?
What is the best approach for Root Equals Sum of Children?
Is Root Equals Sum of Children asked at Google/Amazon/Meta?
What data structure is used in Root Equals Sum of Children?
What is the time complexity of Root Equals Sum of Children?
Ready to solve this problem?
Practice Root Equals Sum of Children with our built-in code editor and test cases.
Practice on FleetCode