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.