Lecture 182:-K-Sum Paths

Finding K-sum paths in a binary tree involves identifying paths within the tree where the sum of node values along the path is equal to a given target value K. These paths may start and end at any node in the tree.

Here's a Python implementation to find K-sum paths in a binary tree:

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def find_k_sum_paths(root, target_sum): def dfs(node, path): if node is None: return path.append(node.data) current_sum = 0 # Check for valid paths ending at the current node for i in range(len(path) - 1, -1, -1): current_sum += path[i] if current_sum == target_sum: print("Path:", path[i:]) dfs(node.left, path.copy()) dfs(node.right, path.copy()) dfs(root, []) # Example usage root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(-3) root.left.left = TreeNode(3) root.left.right = TreeNode(2) root.right.right = TreeNode(11) root.left.left.left = TreeNode(3) root.left.left.right = TreeNode(-2) root.left.right.right = TreeNode(1) target = 8 print("K-Sum Paths with target", target, ":") find_k_sum_paths(root, target)

In this example, the TreeNode class represents nodes of the binary tree. The find_k_sum_paths function takes a root node and a target sum target_sum as inputs and recursively searches for K-sum paths using a depth-first search (DFS) approach.

The dfs function performs the recursive DFS traversal and maintains a path list that holds the values of nodes encountered along the current path. It checks for valid K-sum paths ending at the current node by calculating the cumulative sum of values along the path and comparing it with the target sum. If a valid path is found, it prints the path.

The example usage section demonstrates how to find K-sum paths with a given target value in a binary tree.

Keep in mind that this implementation prints the paths as sequences of values. Depending on your use case, you can modify the implementation to return or store the paths in a more structured format if needed.