Scale Engineer

Root Equals Sum of Children

Easy
#2037Time: O(1). The number of operations is constant as the tree size is fixed at 3. We perform a fixed number of additions to the queue and the loop runs exactly twice.Space: O(1). The queue stores at most two elements, so the space used is constant and does not depend on the input values.
Data structures
TreeBinary Tree

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This method employs a standard iterative tree traversal technique, specifically Breadth-First Search (BFS), using a queue. We add the root's children to a queue, then process the queue to sum their values. This approach is functionally correct but is considered inefficient for this problem due to its unnecessary complexity and overhead.

Algorithm

  • Initialize a sum variable to 0.
  • Create a Queue to store the children of the root.
  • Add the left and right children to the queue. The problem statement guarantees they exist.
  • Loop while the queue is not empty:
    • Dequeue a node.
    • Add the node's value to the sum.
  • After the loop, compare the sum with the root's value and return the result.

Walkthrough

The algorithm works as follows:

  1. A queue is initialized to hold tree nodes.
  2. The left and right children of the root are added to the queue. Since the problem guarantees these children exist, we don't need null checks.
  3. A variable childrenSum is initialized to 0.
  4. We then loop until the queue is empty, dequeuing each child and adding its value to childrenSum.
  5. Finally, we compare root.val with childrenSum and return the boolean result. While this is a robust method for general tree traversal, it's overkill for a fixed 3-node tree.
/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */import java.util.LinkedList;import java.util.Queue; class Solution {    public boolean checkTree(TreeNode root) {        if (root == null) {            return false;        }                Queue<TreeNode> children = new LinkedList<>();        // The problem guarantees the children exist.        children.add(root.left);        children.add(root.right);                int sum = 0;        while(!children.isEmpty()) {            TreeNode child = children.poll();            sum += child.val;        }                return root.val == sum;    }}

Complexity

Time

O(1). The number of operations is constant as the tree size is fixed at 3. We perform a fixed number of additions to the queue and the loop runs exactly twice.

Space

O(1). The queue stores at most two elements, so the space used is constant and does not depend on the input values.

Trade-offs

Pros

  • It's a generic approach that demonstrates a standard tree traversal algorithm (BFS).

Cons

  • Introduces unnecessary overhead from using a Queue data structure.

  • The code is more verbose and less clear than a direct solution.

  • It's computationally slower in practice due to method calls for queue operations, even though the Big O complexity is the same.

Solutions

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean checkTree ( TreeNode root ) { return root . val == root . left . val + root . right . val ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem