The Weekly Challenge 057

Invert Tree and Shortest Unique Prefix

Solutions on GitHub

Task 1: Invert Tree

You are given a binary tree. Write a script to invert the binary tree (mirror image).

Example Output

Original tree: |--7 |--3 |--6 1 |--5 |--2 |--4 Inverted tree: |--4 |--2 |--5 1 |--6 |--3 |--7

Logic

Swap the left and right child nodes at the root node, then recursively invert the left and right subtrees.

Perl Solution

ch-1.pl

package BinaryTree; sub invert { my $self = shift; ( $self->{left}, $self->{right} ) = ( $self->{right}, $self->{left} ); $self->{left}->invert() if defined $self->{left}; $self->{right}->invert() if defined $self->{right}; }

Python Solution

ch-1.py

class BinaryTree: def invert(self): self.left, self.right = self.right, self.left if self.left: self.left.invert() if self.right: self.right.invert()

Task 2: Shortest Unique Prefix

Write a script to find the shortest unique prefix for each word in a given list of words.

Example Output

Input: ["alphabet", "book", "carpet", "cadmium", "cadeau", "alpine"] Output: ["alph", "b", "car", "cadm", "cade", "alp"]

Logic

For each word, incrementally expand a prefix character by character until the prefix is unique (i.e. does not match the prefix of any previously determined prefix / word in the list).

Perl Solution

ch-2.pl

sub shortest_unique_prefixes { my @words = @_; my @result; for my $word (@words) { my $prefix = ""; for my $char ( split //, $word ) { $prefix .= $char; if ( !grep { $_ =~ /^$prefix/ } @result ) { push @result, $prefix; last; } } } return \@result; }

Python Solution

ch-2.py

def shortest_unique_prefixes(words: List[str]) -> List[str]: result = [] for word in words: prefix = "" for char in word: prefix += char if not any(res.startswith(prefix) for res in result): result.append(prefix) break return result