💡 Problem Formulation: We need a way to verify in a binary tree whether each non-leaf node’s value is indeed the sum of its children’s values. For instance, given a binary tree where a non-leaf node with a value of 10 has two children with values 4 and 6, our check should return true as 10 equals 4 plus 6.
Method 1: Recursive Approach
This method involves a recursive function that traverses the tree. If the node is null or a leaf, it returns true. Otherwise, it checks if the node’s value is the sum of its children’s values and then recursively checks the children.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def check_sum(node):
if node is None or (node.left is None and node.right is None): # Leaf or null check
return True
left_val = node.left.value if node.left else 0
right_val = node.right.value if node.right else 0
return (node.value == left_val + right_val) and check_sum(node.left) and check_sum(node.right)
# Example Tree
root = Node(10)
root.left = Node(4)
root.right = Node(6)
print(check_sum(root))The output of this code is: True.
This snippet defines a simple binary tree and a function check_sum to recursively verify that each node value, except the leaves, is the sum of its children’s values. It’s a clear and simple recursive descent that checks the required property.
Method 2: Iterative Depth-First Search (DFS)
Iterative DFS uses a stack to simulate the call stack of a recursive approach. It’ll iterate over each node and check the sum condition until the stack is empty.
Here’s an example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def check_sum_iterative(root):
if not root:
return True
stack = [root]
while stack:
node = stack.pop()
if node.left is None and node.right is None:
continue
child_sum = 0
if node.left:
child_sum += node.left.value
stack.append(node.left)
if node.right:
child_sum += node.right.value
stack.append(node.right)
if node.value != child_sum:
return False
return True
# Example Tree
root = Node(10)
root.left = Node(4)
root.right = Node(6)
print(check_sum_iterative(root))The output of this code is: True.
Instead of recursion, this method uses a stack to keep track of the nodes to visit. It iteratively performs the same check as the recursive method, proving its versatility across different implementations.
Method 3: Breadth-First Search (BFS)
Breadth-First Search algorithm uses a queue to traverse the tree by levels from top to bottom. It checks each node’s value against the sum of its children during traversal.
Here’s an example:
from collections import deque
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def check_sum_bfs(root):
if not root:
return True
queue = deque([root])
while queue:
node = queue.popleft()
if node.left is None and node.right is None:
continue
child_sum = 0
if node.left:
child_sum += node.left.value
queue.append(node.left)
if node.right:
child_sum += node.right.value
queue.append(node.right)
if node.value != child_sum:
return False
return True
# Example Tree
root = Node(10)
root.left = Node(4)
root.right = Node(6)
print(check_sum_bfs(root))The output of this code is: True.
This code snippet performs a level order traversal using a queue to check if each node follows our sum condition. It ensures all nodes satisfy the constraint before returning True.
Method 4: Utilizing a Helper Function
This method uses a helper function to abstract some of the logic within the recursive approach, potentially improving readability and making it easier to manage complex logic or additional functionality.
Here’s an example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def is_sum_node(node):
left_val = node.left.value if node.left else 0
right_val = node.right.value if node.right else 0
return node.value == left_val + right_val
def check_sum_with_helper(node):
if node is None or (node.left is None and node.right is None):
return True
if not is_sum_node(node):
return False
return check_sum_with_helper(node.left) and check_sum_with_helper(node.right)
# Example Tree
root = Node(10)
root.left = Node(4)
root.right = Node(6)
print(check_sum_with_helper(root))The output of this code is: True.
In this version, the is_sum_node helper function simplifies the process of checking a node’s value against its children’s sum. The check_sum_with_helper function maintains the structure of the recursive method.
Bonus One-Liner Method 5: Using Lambda Expressions
For the enthusiasts of concise code, Python lambdas can sometimes pack the logic into a one-liner function. This is less readable but can be fun for code golfing.
Here’s an example:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
check_sum_lambda = lambda n: n is None or ((n.left is None and n.right is None) or (n.value == (n.left.value if n.left else 0) + (n.right.value if n.right else 0) and check_sum_lambda(n.left) and check_sum_lambda(n.right)))
# Example Tree
root = Node(10)
root.left = Node(4)
root.right = Node(6)
print(check_sum_lambda(root))The output of this code is: True.
This snippet shows a one-liner lambda function that acts as a drop-in replacement for our recursive sum check method. While compact, it is recommended for smaller and simpler checks due to legibility concerns.
Summary/Discussion
- Method 1: Recursive Approach. Straightforward and elegant. It might hit the recursion depth limit for very deep trees.
- Method 2: Iterative DFS. Provides a non-recursive solution that avoids potential stack overflow issues with recursion, but can be less intuitive.
- Method 3: BFS. It traverses the tree level-by-level and may be more intuitive for some. Requires additional space for the queue proportional to the breadth of the tree.
- Method 4: Helper Function. Encapsulates node sum check logic, which can make the code cleaner and more modular. Adds a bit of overhead but improves readability.
- Method 5: Lambda Expressions. A compact solution that’s not as easily readable. Useful for those preferring concise code but may be harder to maintain.