# 5 Best Ways to Program to Check If Non-Leaf Nodes Sum to Their Children’s Values in Python

Rate this post

π‘ 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.

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.