# 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] == 'l':
if stack[-1].l:
stack.append([stack[-1].l, 'l'])
depth += 1
else:
stack[-1] = 'r'
elif stack[-1] == 'r':
if stack[-1].r:
stack.append([stack[-1].r, 'l'])
depth += 1
else:
stack[-1] = 0
elif stack[-1] == 0:
max_depth = max(max_depth, depth)
stack.pop()
depth -= 1
if stack:
if stack[-1] == 'l':
stack[-1] = 'r'
elif stack[-1] == 'r':
stack[-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. Anonymous says:

1. David says: