Lecture 180:-Transform To Sum Tree

A sum tree is a binary tree in which each node's value is equal to the sum of its left and right subtree values. Transforming a given binary tree into a sum tree involves modifying the tree such that it satisfies the sum tree property.

Here's a Python implementation to transform a binary tree into a sum tree:

pythonCopy code

class TreeNode: def __init__(self, data): self.data = data self.left = None self.right = None def transform_to_sum_tree(root): if root is None: return 0 # Recursively calculate the sum of left and right subtrees left_sum = transform_to_sum_tree(root.left) right_sum = transform_to_sum_tree(root.right) # Store the original value of the current node original_value = root.data # Update the current node's value to the sum of left and right subtrees root.data = left_sum + right_sum # Return the new value of the current node return root.data + original_value def inorder_traversal(root): if root: inorder_traversal(root.left) print(root.data, end=" ") inorder_traversal(root.right) # Example usage root = TreeNode(10) root.left = TreeNode(-2) root.right = TreeNode(6) root.left.left = TreeNode(8) root.left.right = TreeNode(-4) root.right.left = TreeNode(7) root.right.right = TreeNode(5) print("Original Tree:") inorder_traversal(root) print() transform_to_sum_tree(root) print("Sum Tree:") inorder_traversal(root)

In this example, the TreeNode class represents nodes of the binary tree. The transform_to_sum_tree function transforms the given binary tree into a sum tree by recursively calculating the sum of left and right subtrees and updating each node's value. The original_value variable is used to temporarily store the original value of the current node before updating it.

The inorder_traversal function performs an in-order traversal to print the tree before and after transformation.

Keep in mind that transforming a tree to a sum tree is just one type of tree transformation. Depending on the problem, you might need to perform different types of tree transformations or modifications.