💡 Problem Formulation: In binary tree data structures, it’s a common requirement to calculate the sum of all node values. Given a binary tree, we aim to compute the cumulative value of all its nodes. For instance, in a tree with nodes containing values 1, 2, and 3, the desired output is 6.
Method 1: Recursive Pre-order Traversal
A recursive pre-order traversal involves visiting the root node, then recursively summing the values in the left subtree, followed by the right subtree. Ultimately, the local sums are combined to produce the overall sum of the tree. It’s an intuitive and widely used approach for tree problems.
Here’s an example:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def sum_of_nodes(node):
if node is None:
return 0
return node.value + sum_of_nodes(node.left) + sum_of_nodes(node.right)
# Example usage
root = TreeNode(1, TreeNode(2), TreeNode(3))
print(sum_of_nodes(root))
Output: 6
This code defines a simple binary tree and computes the sum of its nodes using recursion. It captures the essence of pre-order traversal: process the root, then left, then right.
Method 2: Iterative Depth-First Search (DFS)
Iterative DFS techniques employ a stack to emulate the call stack used in recursion. They systematically explore the nodes of the tree, accumulating their values, akin to manually executing a recursive algorithm.
Here’s an example:
def sum_of_nodes_iterative(node):
if node is None:
return 0
stack, total_sum = [node], 0
while stack:
current = stack.pop()
total_sum += current.value
if current.right:
stack.append(current.right)
if current.left:
stack.append(current.left)
return total_sum
# Example usage
print(sum_of_nodes_iterative(root))
Output: 6
This snippet demonstrates how to calculate the nodes’ sum without recursion but by using iterative DFS. The stack drives the traversal, ensuring no node is left unvisited.
Method 3: Iterative Breadth-First Search (BFS)
Iterative BFS traverses the tree level by level, employing a queue. Visiting nodes in this manner guarantees a systematic approach—every node is accessed and its value included in the sum, much like taking inventory aisle by aisle.
Here’s an example:
from collections import deque
def sum_of_nodes_bfs(node):
if node is None:
return 0
queue, total_sum = deque([node]), 0
while queue:
current = queue.popleft()
total_sum += current.value
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return total_sum
# Example usage
print(sum_of_nodes_bfs(root))
Output: 6
In this code example, the breadth-first search algorithm computes the sum of the nodes. The use of a queue helps traverse the tree level by level.
Method 4: Using Morse Traversal
Morris traversal provides a way to traverse a tree without using extra space for a stack or queue. This is achieved by threading the tree during traversal, creating temporary links between nodes. It’s especially beneficial in terms of space complexity.
Here’s an example:
def sum_of_nodes_morris(node):
total_sum = 0
current = node
while current:
if current.left is None:
total_sum += current.value
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right is not current:
predecessor = predecessor.right
if predecessor.right is None:
predecessor.right = current
current = current.left
else:
predecessor.right = None
total_sum += current.value
current = current.right
return total_sum
# Example usage
print(sum_of_nodes_morris(root))
Output: 6
This code elegantly sidesteps the use of additional memory by using the Morris traversal, creating temporary links to maintain awareness of the tree’s structure.
Bonus One-Liner Method 5: Pythonic Recursive Wag
The beauty of Python allows us to condense algorithms into incredibly concise expressions. The following one-liner captures the essence of the recursive approach with minimal syntax. Suitable for small trees where code brevity is preferred over readability.
Here’s an example:
sum_of_nodes = lambda node: node.value + sum_of_nodes(node.left) + sum_of_nodes(node.right) if node else 0 # Example usage print(sum_of_nodes(root))
Output: 6
This one-liner is a Pythonic approach, using a lambda function to concisely perform the summation in a recursive manner, demonstrating the power and elegance of Python’s syntax.
Summary/Discussion
- Method 1: Recursive Pre-order Traversal. Intuitive and easy to implement. However, it’s not space-efficient due to the call stack size in deep trees.
- Method 2: Iterative DFS. Uses a stack to emulate recursion, saving space for balanced trees. Can be more complex than recursive solutions.
- Method 3: Iterative BFS. Traverses the tree level by level. Memory usage can grow quickly with the tree width.
- Method 4: Morris Traversal. Space-efficient for in-order traversal, complexity hides in threading and unthreading nodes.
- Method 5: Pythonic Recursive Wag. Extremely concise, great for small trees, but lacks clarity for readers unfamiliar with Python succinctness.