TreeHeight

This page shows two solutions to the question TreeHeight made by Codility in the lesson 99 “ Future Training”.

def solution(T):
    if T:
        return max( solution(T.l), solution(T.r) ) +1
    return -1

Correctness is 100%. Performance is not assessed.

However, a different solution which does not use recursion is:

from extratypes import Tree  # library with types used in the task

def solution(T):
    stack = [[T, 'l']]
    max_depth = depth = 0
    while True:
        if stack[-1][1] == 'l':
            if stack[-1][0].l:
                stack.append([stack[-1][0].l, 'l'])
                depth += 1
            else:
                stack[-1][1] = 'r'
        elif stack[-1][1] == 'r':
            if stack[-1][0].r:
                stack.append([stack[-1][0].r, 'l'])
                depth += 1
            else:
                stack[-1][1] = 0
        elif stack[-1][1] == 0:
            max_depth = max(max_depth, depth)
            stack.pop()
            depth -= 1
            if stack:
                if stack[-1][1] == 'l':
                    stack[-1][1] = 'r'
                elif stack[-1][1] == 'r':
                    stack[-1][1] = 0
            else: 
                return max_depth

Correctness is 100%. Performance is not assessed.

In both cases, the worst-case time complexity is O(N) where N is the number of nodes of the input tree “T”.

The recursive solution performs a breadth first search. The iterative solution performs a depth first search.

2 Replies to “TreeHeight”

    1. Apologies, I don’t know why that happens.

      On Codility’s web site that line appears in the box where you are meant to type the solution, and that’s why I also pasted it here alongside the second solution. But, to be honest, I don’t even know why Codility decided to add that line; the solutions on this page do not need that line.

Leave a Reply

Your email address will not be published.