Task — Recreate binary tree

You are given a Binary Tree. Write a script to replace each node of the tree with the sum of all the remaining nodes.

Examples

Example 1
Input:
        1
       / \
      2   3
     /   / \
    4   5   6
     \
      7
Output:
        27
       /  \
      26  25
     /   /  \
    24  23  22
     \
     21

Analysis

The generation of the output node values is simple: add all the node values ($node) together ($sum)and then replace each node with $sum - $node

What is much harder is displaying the input and output trees, but I achieved that by creating a rectangular array $f with each cell populated with $w + 1 spaces, where $w is the width of the widest node value.

It is then possible, though tricky, to populate that with the node values and some / | \ symbols to show the tree branches.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-17
use utf8;     # Week 113 - task 2 - Recreate binary tree
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

recreate_binary_tree([[1], [2, 3], [4, undef, 5, 6], [undef, 7]]);
recreate_binary_tree([[1], [2, 3], [4, 9, 5, 6], [11, 12, 13, 14, 15, 16, 17, 18],
    [21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36]]);
recreate_binary_tree([[123], [234, 345], [41, undef, 51, 61], [undef, 7]]);

sub recreate_binary_tree {

    my ($col, $cols, $node, $row, $rows, $sum, $tree);

    # initialise
    $tree = $_[0];
    $rows = @$tree;
    $cols = (2 ** $rows) - 1;
    
    say qq[\nInput: ];
    print_binary_tree($tree);
    
    # get sum of nodes
    for $row (0 ..$rows - 1) {
        for $col (0 .. 2 ** ($row + 1)) {
            $sum += $tree->[$row]->[$col] if defined $tree->[$row]->[$col];
        }
    }
    
    # update nodes
    for $row (0 .. $rows - 1) {
        for $col (0 .. 2 ** ($row + 1)) {
            $node = \$tree->[$row]->[$col];
            $$node = $sum - $tree->[$row]->[$col] if defined $$node;
        }
    }
    
    # report
    say qq[\nOutput:];
    print_binary_tree($tree);
}

sub print_binary_tree {

    my ($col, $cols, $fcol, $frow, $offset, $node, $offset2, $row, $rows, $s,
        $tree, $up_row, $w, @f, @next, @this);
    
    # initialise
    $tree = $_[0];
    $rows = @$tree;
    $cols = (2 ** $rows) - 1;
    
    # get (max) width of elements
    $w = 0;
    for $row (0 .. $rows - 1) {
        for $col (0 .. 2 ** $row) {
            $node = \$tree->[$row]->[$col];
            $w = length($$node) if (defined $$node and length($$node) > $w);
        }
    }
        
    # blank area
    $s = ' ' x $w;
    for $frow (0 .. 2 * $rows - 2) {
        for $fcol (0 .. $cols - 1) {
            $f[$frow][$fcol] = $s;
        }
    }
    
    # populate area
    @next = ($cols + 1) / 2 - 1;
    $offset = 2 ** ($rows - 2);
    
    for $row (0 .. $rows - 1) {
        $frow = 2 * $row;
        $up_row = $rows - $row;
        
        # @this is the list of horizontal positions for the row
        @this = @next;
        @next = ();
        
        for $col (0 .. 2 ** $row - 1) {
            
            # data row
            $fcol = shift @this;
            if (defined $tree->[$row]->[$col]) {
                $f[$frow][$fcol] = sprintf("%-${w}d", $tree->[$row]->[$col]);
            } else {
                $f[$frow][$fcol] = substr('~' . ' ' x 10, 0, $w);
            }
            push @next, $fcol - $offset, $fcol + $offset;
                
            # symbol row
            if ($row < $rows - 1) {
                $offset2 = int($offset / 2);
                $f[$frow + 1][$fcol - $offset2] = 
                    $row == $rows - 2 ? substr('|' . ' ' x 10, 0, $w) : 
                    substr('/' . ' ' x 10, 0, $w);
                $f[$frow + 1][$fcol + $offset2] = 
                    $row == $rows - 2 ? substr('|' . ' ' x 10, 0, $w) : 
                    substr('\\' . ' ' x 10, 0, $w);
            }
        }
        $offset /= 2;
    }

    # print
    for $frow (0 .. 2 * $rows - 2) {
        for $fcol (0 .. $cols - 1) {
            print $f[$frow][$fcol];
        }
        say '';
    }
}

58 lines of code

I completed this challenge after the closing date
and it has not been submitted to GitHub