Watch 10 video solutions for Root Equals Sum of Children, a easy level problem involving Tree, Binary Tree. This walkthrough by CodeClips with Abhishek Ranjan has 1,330 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
-100 <= Node.val <= 100Problem 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 | 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. |