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).

Quick solution in C# (left in some code that I refactored out)… 100%

What is the problem for this? It says tree height but it doesn’t look like the tree height problem I had on the test. Which was to make the minimum number of cuts so that trees have heights going up and down alternately. If it is for that problem then I’m somewhat lost.

I do not know what is your test. In the original post, there is a link to the question. Please refer to it.