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.