You are given a list of integers. Consider a tree where arr represents the values of its leaves in
an inorder traversal. Internal nodes have 2 children and their value is equal to the product of the
largest leaf value of its left subtree and the largest leaf value of its right subtree.
Your task is to find the tree with the minimum sum of its values and write the sum in the output
file.
For example, given [2, 3, 5], the minimum sum tree is
The leaf nodes are 2,3, and 5 also Internal nodes have 2 children and their value is equal to the
product of the largest leaf value of its left subtree and the largest leaf value of its right subtree.
6 is formed by the product of the largest leaf values from the left(2) and right(3) sub-tree: 2X3 = 6
and same for root which is the product of the largest leaf values from the left(3) and right(5)
sub-tree: 3X5 = 15
The output should be the sum of all the nodes 15+6+5+2+3 = 31
Your algorithm should work in time complexity of n**2 or better.
Remember:
Every node has 2 children except the leaf nodes!
You are required to use the TreeNode Data Structure
# Tree Node Data structure
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Requirements:
1. Read the input from a file(inputPS2.txt), where each line is a space-separated list of
integers (always positive) which represents the values of its leaves in an inorder
traversal.
2. You will output your answers to a file (outputPS2.txt) for each line.
3. Don’t use any external libraries. Anything that comes with plain Python is allowed. (If
you have to do pip install anything you cannot use it).
4. Create a single *.py file for code, do not fragment your code into multiple files OR
submit a Jupyter Notebook.(no *.ipynb)
5. Perform an analysis for the features above and give the running time in terms of input
size: n.
6. Implement the above problem statement using Python 3.7.
Sample Input:
Input will be taken from the file(inputPS2.txt) here each line is a space-separated list of integers
(always positive) which represents the values of its leaves in an inorder traversal.
2 3 5
Note that the input data shown here is only for understanding and testing, the actual file used for
evaluation will be different.
Sample Output:
For every line in the input find the tree with the minimum sum of its values and write the sum in
the output file.
31
Note that the input/output data shown here is only for understanding and testing, the actual file
used for evaluation will be different.
Display the output in outputPS2.txt.