Question: https://codility.com/demo/take-sample-test/tree_height

Question Name: TreeHeight

Classic recursion problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
def solution(T): if T.l == None and T.r == None: # Has no subtree return 0 elif T.l == None: # Only has right subtree return 1 + solution(T.r) elif T.r == None: # Only has left subtree return 1 + solution(T.l) else: # Have two subtrees return 1 + max(solution(T.l), solution(T.r)) |

Java version:

Thanks for sharing your solution!

For posting code, please add the code inside a <pre> </pre> section, rather than <code> </code>.

BTW, the first Math.max is not necessary.

Or more simply

Elegant solution! Thank you!

Hi Guys! I thought about doing this solution too but isn’t this n^2 time complexity ?

In the end the performance of my test was not assessed, but other solutions I tried before with recursion were always a bit slow.

Miguel

>> binary tree T consisting of N nodes

The code access each node, once and only once. Therefore the complexity is O(N).