Root Equals Sum of Children — Solution in Python, Java & C++
Root Equals Sum of Children solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on trees.
Root Equals Sum of Children is an easy coding problem on trees, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Trees
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary tree that has exactly three nodes: the root, its left child and its right child.
Return true if the root's value equals the sum of its two children's values, and false otherwise.
Example 1
Input: root = [10,4,6]
Output: true
Explanation: 4 + 6 = 10.
Example 2
Input: root = [5,3,1]
Output: false
Explanation: 3 + 1 = 4, not 5.
Example 3
Input: root = [0,-7,7]
Output: true
Explanation: -7 + 7 = 0.
Constraints
the tree has exactly 3 nodes: root, root.left and root.right-100 <= Node.val <= 100
Hints for Root Equals Sum of Children
Hint 1
The shape is fixed, so there is nothing to traverse.
Hint 2
Both children are guaranteed to exist.
Hint 3
Compare
root.valwithroot.left.val + root.right.val.
How to solve Root Equals Sum of Children
With the shape guaranteed, the question is one comparison between the root and its two children.
Approach
- Read the left child's value and the right child's value.
- Return whether their sum equals the root's value.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Values may be negative; the sum is still a plain integer sum.
Reference solution
Python
from typing import Optional
def checkTree(root: Optional[TreeNode]) -> bool:
return root.val == root.left.val + root.right.valJava
public static boolean checkTree(TreeNode root) {
return root.val == root.left.val + root.right.val;
}C++
bool checkTree(TreeNode* root) {
return root->val == root->left->val + root->right->val;
}JavaScript
var checkTree = function(root) {
return root.val === root.left.val + root.right.val;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 155 trees problems · the whole catalogue
Learn the technique: Binary Trees and Tree Traversals