Challenge 151 Task #1 - Binary Tree Depth

[Task #1] - Binary Tree Depth

Description

You are given binary tree.

Write a script to find the minimum depth.

The minimum depth is the number of nodes from the root to the nearest leaf node (node without any children).

Example 1:

Input: '1 | 2 3 | 4 5'

                1
               / \
              2   3
             / \
            4   5

Output: 2

Example 2:

Input: '1 | 2 3 | 4 *  * 5 | * 6'

                1
               / \
              2   3
             /     \
            4       5
             \
              6
Output: 3

Solution

Full Source

This week’s challenges were a little unusual for me. Usually the first task is easier and takes less time to implement. This week I spent way more time one the first than on the second task.

To make processing of the input easier, I tokenize it before starting to calculate the minimum depth. After the tokenization process we are left with a list of Value-, PlaceHolder- and SeparatorTokens. I won’t illustrate this process here further. It’s pretty straightforward, if you’re interested you can check it out in the source linked above.

To determine the minimum depth we walk the list of tokens and built up our binary tree. We stop processing on the first node without children or when we run out if input. In the case were we used up all input, we have completely parsed the whole tree and the wanted depth is the total depth of the tree. To represent the tree we’re using an array of arrays, each representing a layer of the tree. For each layer we want 2 to the power of the layer’s depth elements. If we run out of tokens or encounter a separator token before a layer is complete, we fill it with placeholders. For ValueTokens we check if the parent node is defined, and add their value to the tree. If the parent is missing the process will be aborted with an error message indicating where the invalid value was in the input. The placeholders will add an undefined value to the tree. For placeholders on even positions we also check their left neighbor is also a placeholder, and if there is a parent node for that position. If these conditions hold we found a node without children (the current parent). We stop processing and return the current depth as our result.

Have some code:

sub minimum_binary_tree_depth ( @tokens) {
    my $depth = 0;
    my $tree  = [];

    while (@tokens) {
        push @$tree, [];
        my $num_elems = 2**$depth;
        for ( my $i = 0 ; $i < $num_elems ; $i++ ) {

            if ( !@tokens || $tokens[0]->isa('SeperatorToken') ) {
                ## fill row with dummy placeholder tokens.
                unshift @tokens,
                  map { PlaceHolderToken->new(-1) }
                  0 .. ( $num_elems - 1 - $i );
            }

            my $cur = shift @tokens;
            if ( $cur->isa('ValueToken') ) {
                if ( $depth && !defined( $tree->[-2][ int( $i / 2 ) ] ) ) {
                    die join( " ",
                        "Missing parent for node with value",
                        $cur->{lexeme},
                        "at position",
                        $cur->pos_human_readable(),
                        "in input\n" );
                }
                push @{ $tree->[-1] }, $cur->{lexeme};
            }
            elsif ( $cur->isa('PlaceHolderToken') ) {
                if (   $i % 2
                    && !defined $tree->[-1][-1]
                    && ( !$depth || defined $tree->[-2][ int( $i / 2 ) ] ) )
                {
                    return $depth;
                }
                push @{ $tree->[-1] }, undef;
                ## do nothing
            }
        }

        $depth += 1;

        # handle optional seperatortoken
        if ( @tokens && $tokens[0]->isa("SeperatorToken") ) {
            shift @tokens;
        }
    }

    return $depth;
}

There is no comment section on this site. For questions, suggestions or errors in my post or solution, please create an issue over here or drop me a mail:

    
my $mail = join('@', 'pwc', join('.', 'pankoff', 'net'));