Root Equals Sum of Children solution and explanation
Google
9 more videos on this problem
Root Equals Sum of Children | LeetCode 2236 | CppCodeClips with Abhishek Ranjan · 1:42 · 1K views
Root Equals Sum of Children - LeetCode 2236 Solution in C++ (LeetCode Math)nexTRIE · 2:13 · 1K views
2236. Root Equals Sum of Children | Leetcode Solutionpredecode · 4:10 · 786 views
Root Equals Sum of Children - LeetCode 2236 - Java Solutionalgobest - Computer Science · 2:46 · 638 views
LeetCode#2236 Root Equals Sum of Children - PythonCodeJulian · 0:36 · 612 views
Solving LeetCode problem 2236 in APL (Root Equals Sum of Children)Rodrigo's APL Corner · 4:32 · 468 views
2236. Root Equals Sum of ChildrenAyan this side · 2:45 · 330 views
2236. Root Equals Sum of Children | LEETCODE EASY | BINARY TREEcode Explainer · 2:01 · 308 views
LeetCode 2236 | Root Equals Sum of Children | Binary Tree | JavaSleepy Cracker · 3:27 · 186 views
Leetcode 2236AUM · 5:20 · 73 views
The problem
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
Approach overview
Problem 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 1: Simple Direct Access and Comparison
This approach leverages the simplicity of the tree structure, which consists of exactly three nodes. We directly access the left and right children of the root node and compare their sum to the root node's value. This approach works efficiently given the constraint of only 3 nodes.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def checkTree(self, root: TreeNode) -> bool:
return root.val == root.left.val + root.right.valclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean checkTree(TreeNode root) {
return root.val == (root.left.val + root.right.val);
}
}class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool checkTree(TreeNode* root) {
return root->val == (root->left->val + root->right->val);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function checkTree(root) {
return root.val === (root.left.val + root.right.val);
}#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool checkTree(struct TreeNode* root){
return root->val == (root->left->val + root->right->val);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool CheckTree(TreeNode root) {
return root.val == (root.left.val + root.right.val);
}
}In Python, we define a TreeNode class with an initializer for root, left, and right nodes. The function checkTree returns whether the root node's value is the sum of its children's values by accessing their attributes directly.
Time Complexity: O(1) - The operation is performed in constant time.
Space Complexity: O(1) - There's no additional space allocation.
Approach 2: Defensive Programming
This approach is similar to the first but includes basic defensive programming by handling potential null pointers. Though the tree constraints guarantee non-null children, it showcases safe coding practices.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def checkTree(self, root: TreeNode) -> bool:
if not root or not root.left or not root.right:
return False
return root.val == root.left.val + root.right.valclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean checkTree(TreeNode root) {
if (root == null || root.left == null || root.right == null) return false;
return root.val == (root.left.val + root.right.val);
}
}class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool checkTree(TreeNode* root) {
if (!root || !root->left || !root->right) return false;
return root->val == (root->left->val + root->right->val);
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
function checkTree(root) {
if (!root || !root.left || !root.right) return false;
return root.val === (root.left.val + root.right.val);
}#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool checkTree(struct TreeNode* root){
if (!root || !root->left || !root->right) return false;
return root->val == (root->left->val + root->right->val);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool CheckTree(TreeNode root) {
if (root == null || root.left == null || root.right == null) return false;
return root.val == (root.left.val + root.right.val);
}
}In this Python solution, we utilize checks for non-None nodes, which isn't strictly needed given the constraints but adheres to good coding practice. After validation, a straightforward value comparison is made.
Time Complexity: O(1) - Basic operations occur instantly.
Space Complexity: O(1) - Nothing beyond initial input is stored.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function checkTree(root: TreeNode | null): boolean {
return root.val === root.left.val + root.right.val;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func checkTree(root *TreeNode) bool {
return root.Val == root.Left.Val+root.Right.Val
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn check_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
let node = root.as_ref().unwrap().borrow();
let left = node.left.as_ref().unwrap().borrow().val;
let right = node.right.as_ref().unwrap().borrow().val;
node.val == left + right
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simple Direct Access and Comparison | Time Complexity: O(1) - The operation is performed in constant time. |
| Defensive Programming | Time Complexity: O(1) - Basic operations occur instantly. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Root Equals Sum of Children easy or hard?
Root Equals Sum of Children is classified as an Easy problem. It focuses on understanding binary tree node access and simple arithmetic comparison rather than traversal or advanced algorithms.
Root Equals Sum of Children Python/Java solution
The Python or Java solution reads the values of the root and its children and returns whether root.val equals root.left.val plus root.right.val. The logic is identical across languages and runs in O(1) time and O(1) space.
How to solve Root Equals Sum of Children in O(n)?
An O(n) traversal is unnecessary for this problem because the input tree always contains exactly three nodes. The optimal solution directly checks root.val == root.left.val + root.right.val, which runs in O(1) time and O(1) space.
What is the best approach for Root Equals Sum of Children?
The best approach is direct comparison of the root value with the sum of its two children. Access root.val, root.left.val, and root.right.val, compute the sum of the children, and compare it to the root. The algorithm runs in O(1) time and O(1) space because only three nodes are involved.
Is Root Equals Sum of Children asked at Google/Amazon/Meta?
This problem is categorized as an easy binary tree question and appears in interview practice sets for companies like Amazon and Google. It is commonly used to test familiarity with tree node structures and basic conditional logic.
What data structure is used in Root Equals Sum of Children?
The problem uses a binary tree data structure. Each node contains a value and references to left and right child nodes. The solution simply reads values from these nodes without performing traversal.
What is the time complexity of Root Equals Sum of Children?
The time complexity is O(1). The solution performs a constant number of operations by reading the values of the root and its two children and comparing them. No traversal or iteration over the tree is required.