Check That Every Node Equals Its Descendant Sum
Updated
Problem statement
You are given the root of a binary tree. For a node, its descendants are all the nodes below it: its children, their children, and so on.
Return true if every node that has at least one child has a value equal to the sum of the values of all its descendants. Otherwise, return false.
A leaf has no descendants, so a leaf always passes, whatever its value. In particular, a tree with a single node is always valid.
Note that comparing a node only with its two children is not enough: the grandchildren and every deeper node count too.
Function
isSumTree(root: TreeNode) → booleanExamples
Example 1
root = [18,6,3,2,4,null,3]return = trueThe leaves 2, 4 and the lower 3 have no descendants, so they are fine. Node 6 has descendants 2 and 4, and 2 + 4 = 6. The upper node 3 has one descendant, the leaf 3, so it matches. The root's descendants are 6, 3, 2, 4 and 3, and 6 + 3 + 2 + 4 + 3 = 18.
Example 2
root = [10,6,4,2,4]return = falseNode 6 matches its descendants (2 + 4 = 6), and the leaves are fine. The root equals the sum of its two children, 6 + 4 = 10, but that is not enough: its descendants are 6, 4, 2 and 4, which add up to 16, not 10. So the answer is false.
Example 3
root = [-7]return = trueA single node has no descendants, so it always satisfies the rule, whatever its value.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -10^4 <= Node.val <= 10^4
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Count One-Valued Regions in a Binary TreeGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maximum Depth of Binary TreeLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Path SumSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Binary Tree Preorder TraversalAnduril · ONSITE INTERVIEWAnduril interview questions
- Root-to-Node Path in a Binary TreeAmazon · ONSITE INTERVIEW
- Symmetric Binary TreeFigma · ONSITE INTERVIEWFigma interview questions
- Tree Level with the Most NodesBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Diameter of a Binary TreeMeta · ONSITE INTERVIEWMeta interview questions
- Mirror Image Binary TreesExpedia · ONSITE INTERVIEWExpedia interview questions
- All Tree Nodes at the Same DepthAMD · ONSITE INTERVIEWAMD interview questions