Root Equals Sum of Children

Easy
1886.

Root Equals Sum of Children

Root Equals Sum of Children is an easy coding problem on trees, asked in Amazon interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var checkTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    The shape is fixed, so there is nothing to traverse.

  2. Hint 2

    Both children are guaranteed to exist.

  3. Hint 3

    Compare root.val with root.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

  1. Read the left child's value and the right child's value.
  2. 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.val

Java

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