Binary Tree Node Sum

Binary Tree Node Sum refers to finding the sum of all the values in a binary tree. It involves traversing the tree and adding up the values of each node.

Example: Let's create a binary tree and calculate the sum of all the nodes' values.

# Node class definition
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Create a binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Calculate the sum of all nodes' values
def node_sum(node):
    if node is None:
        return 0
    return node.value + node_sum(node.left) + node_sum(node.right)

sum_of_nodes = node_sum(root)
print("Sum of nodes:", sum_of_nodes)
# Output: Sum of nodes: 15

In this example, we define a Node class that represents a node in the binary tree. Each node has a value, left child, and right child.

We create a binary tree with the given values.

To calculate the sum of all nodes' values, we define a recursive function node_sum that takes a node as an argument. In this function, we first check if the current node is None. If so, we return 0, as there are no nodes to add.

If the current node is not None, we recursively call node_sum on the left and right children of the current node, and add the value of the current node. We return the sum of the current node's value, the sum of the left subtree, and the sum of the right subtree.

Finally, we call node_sum on the root node of the binary tree and store the result in sum_of_nodes. We print the sum of all nodes' values.

Competitive Question Solution: Let's solve a medium-level competitive question from LeetCode using the concept of Binary Tree Node Sum. The question is "Path Sum," which requires determining if there exists a root-to-leaf path in a binary tree where the sum of all nodes' values is equal to a given target sum.


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    def has_path_sum(self, root, target_sum):
        if root is None:
            return False
        if root.left is None and root.right is None and root.value == target_sum:
            return True
        return (self.has_path_sum(root.left, target_sum - root.value) or
                self.has_path_sum(root.right, target_sum - root.value))

# Create an instance of Solution
solution = Solution()

# Create a binary tree
root = Node(5)
root.left = Node(4)
root.right = Node(8)
root.left.left = Node(11)
root.right.left = Node(13)
root.right.right = Node(4)
root.left.left.left = Node(7)
root.left.left.right = Node(2)
root.right.right.right = Node(1)

# Check if there exists a path with sum = 22
has_path = solution.has_path_sum(root, 22)
print(has_path)
# Output: True

In this solution, we define a Node class to represent a node in the binary tree. We also define a Solution class that contains the has_path_sum method to check if there exists a root-to-leaf path in the binary tree with the given target sum.

The has_path_sum method is implemented using a recursive approach. It performs the following checks:

  • If the root is None, it means we have reached a null node, so we return False.
  • If the root is a leaf node (both left and right children are None), and its value is equal to the target sum, we have found a path with the desired sum, so we return True.
  • We recursively check if there exists a path with the target sum in either the left subtree or the right subtree. To do this, we subtract the value of the current node from the target sum and call has_path_sum on the left and right children.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(h), where h is the height of the binary tree. In the worst case, the height of the tree is O(n), resulting in O(n) space complexity due to the recursion stack.

Next Post Previous Post