You are given a Binary Tree.
Write a script to replace each node of the tree with the sum of all the remaining nodes.
1 / \ 2 3 / / \ 4 5 6 \ 7
27 / \ 26 25 / / \ 24 23 22 \ 21
I have two major issues with the "binary tree" part of the problem.
First, and we have seen this problem before, the author of the problem
couldn't be bothered to state how the binary tree is given. Worse, the
author gave an utterly useless example, carefully crafted to work exactly
for the given input. But what if we were to make a tiny change? Suppose
the 7 was a right child of 2? Then what? How would that tree look like?
Second, what does having the input as a binary tree actually contribute to the problem? We have a set of numbers, and we need to replace each number with the difference of the sum of all the numbers, and said number. It does not matter one iota whether the numbers are in a tree (let alone how they are distributed in a tree), or in a list, or in an array. We'd still get the set of numbers as output.
We therefore decide to completely ignore the binary tree aspect of the problem. We take sets of numbers: each line of standard input is taken as a different set of whitespace separated numbers, and we write the result to standard output, one set on each line.
use List::Util qw [sum];
while (<>) {
my $sum = sum my @num = /-?[0-9]+/g;
say join " " => map {$sum - $_} @num;
}
Not much to see here. For each line of input, we first grep all the
numbers (/-?[0-9]+/g), store them in an array (@num), and
we calculate the sum (my $sum = sum my @num).
Then we print the results by replacing all numbers with the difference of the sum of all the numbers and said number.
Find the full program on GitHub.
We've implemented similar solutions in different languages: AWK, Bash, C, Lua, Node.js, Python, and Ruby.