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.
This package is not being downloaded “from extratypes import Tree”
Any clue?
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.